P4436 [HNOI/AHOI2018]游戏

    • 445通过
    • 1.3K提交
  • 题目提供者 MicDZ
  • 评测方式 云端评测
  • 标签 剪枝 强连通分量,缩点 枚举,暴力 各省省选 2018 安徽 湖南
  • 难度 省选/NOI-
  • 时空限制 1000ms / 512MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    一次小G和小H在玩寻宝游戏,有n个房间排成一列,编号为$1,2,...,n$,相邻的房间之间都有一道门。其中一部分们上锁(因此需要有对应的钥匙才能开门),其余的门都能直接打开。现在小G告诉了小H每把锁的钥匙在哪个房间里(每把锁锁有且只有一把钥匙与之对应),并作出p次指示:第i次让小H从第$S_i$个房间出发到$T_i$个房间里。但是小G有时会故意在指令中放入死路,而小H也不想浪费多余的体力去尝试,于是想事先调查清楚每次的指令是否会存在一条通路。

    你是否能为小H作出解答呢?

    输入输出格式

    输入格式:

    第一行三个数字:$n,m,p$,代表有$n$个房间,$m$道门上了锁,以及$p$个询问。接下来m行,每行两个数字$x,y$代表x到x+1的钥匙在房间$y$。接下来$p$行,其中第i行是两个整数$S_i,T_i$,代表一次询问

    输出格式:

    输出$p$行,每行一个“YES”或"NO",分别代表能或不能到达。

    输入输出样例

    输入样例#1: 复制
    5 4 5 
    1 3
    2 2 
    3 1
    4 4
    2 5
    3 5
    4 5 
    2 1
    3 1
    输出样例#1: 复制
    YES
    NO
    YES
    YES
    NO
    输入样例#2: 复制
    7 5 4
    2 2
    3 3 
    4 2 
    5 3 
    6 6
    2 1
    3 4
    3 7
    4 5
    输出样例#2: 复制
    YES
    YES
    NO
    NO

    说明

    $1\le n,p\le 10^6$,$0\le m <n$,$1\le x,y,S_i,T_i<n$保证x不重复

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