P2189 小Z的传感器

    • 40通过
    • 124提交
  • 题目提供者 LittleZ
  • 评测方式 云端评测
  • 标签 图论 搜索 高性能
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

    众所周知,小 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

    说明

    【数据规模】

    对于 10% 的数据,n ≤ 2;

    对于 30% 的数据,n ≤ 3;

    对于 60% 的数据,n ≤ 10000,m ≤ 20000,k ≤ 10;

    对于 100% 的数据,1 ≤ k ≤ n ≤ 10^5,1 ≤ m ≤ 2 × 10^5,1 ≤ q ≤ 5,x ≠ y。

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。