华师一附中OI组

 找回密码
 立即注册
搜索
热搜: 活动 交友 discuz
查看: 1305|回复: 0
打印 上一主题 下一主题

P2189 小Z的传感器

[复制链接]

738

主题

1485

帖子

5422

积分

管理员

Rank: 9Rank: 9Rank: 9

积分
5422
跳转到指定楼层
楼主
发表于 2018-5-26 21:02:56 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
https://www.luogu.org/problemnew/show/P2189

题目描述
众所周知,小 Z 家是个豪宅,有 n 个房间,并通过 m 条通道相连(家当然是连通的)。

有一天,小 Y 想趁小 Z 不在偷偷光顾他家,并决定到他家的每个房间至少逛一次。不幸的是,小X 家有 k 个房间装了传感器,该传感器会在第一次有人到访的时候返回信息。

当小 Z 回到家时,就发现小 Y 来过了,小 Y 也如实地告诉了小 Z 自己到每个房间至少逛了一次。

然而,小 Z 仔细研究了传感器返回信息的先后顺序,怀疑个别传感器可能返回信息有延迟。

为了验证自己的推断,连同这一次在内,他一共让小 Y 到他家来了 q 次。他想判断每次传感器返回信息的先后顺序是否可能出现,希望你帮帮他。

输入输出格式
输入格式:
第一行包含四个整数 n,m,k,q。

接下来 m 行,每行包含两个整数 x,y,表示房间 x 和房间 y 有一条双向通道相连。

接下来 q 行,每行包含 k 个整数,表示每次按先后顺序返回信息的传感器所在房间的编号。

输出格式:
q 行,每行包含一个字符串“Yes”或“No”,表示每次传感器返回信息的先后顺序是否可能出现。

输入输出样例
输入样例#1:
5 5 3 2
1 2
2 3
3 1
1 4
4 5
4 2 1
4 1 2
输出样例#1:
No
Yes
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

QQ|Archiver|手机版|小黑屋|服务支持:DZ动力|华师一附中OI组  

GMT+8, 2024-12-26 02:32 , Processed in 0.234205 second(s), 23 queries .

Powered by Discuz! X3.2

© 2001-2013 Comsenz Inc.

快速回复 返回顶部 返回列表