P4899 [IOI2018] werewolf 狼人

    • 221通过
    • 458提交
  • 题目提供者 Imagine
  • 评测方式 云端评测
  • 标签 Kruskal 主席树 树状数组 深度优先搜索,DFS IOI 2018 O2优化 高性能
  • 难度 NOI/NOI+/CTSC
  • 时空限制 4000ms / 512MB

题解

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

    最新讨论 显示

    推荐的相关题目 显示

    题目背景

    本题为交互题,但在此请提交完整程序

    题目描述

    在日本的茨城县内共有 $N$ 个城市和 $M$ 条道路。这些城市是根据人口数量的升序排列的,依次编号为 $0$ 到 $N - 1$。每条道路连接两个不同的城市,并且可以双向通行。由这些道路,你能从任意一个城市到另外任意一个城市。

    你计划了 $Q$ 个行程,这些行程分别编号为 $0$ 至 $Q - 1$。第 $i(0 \leq i \leq Q - 1)$ 个行程是从城市 $S_i$ 到城市 $E_i$。

    你是一个狼人。你有两种形态:人形狼形。在每个行程开始的时候,你是人形。在每个行程结束的时候,你必须是狼形。在行程中,你必须要变身(从人形变成狼形)恰好一次,而且只能在某个城市内(包括可能是在 $S_i$ 或 $E_i$ 内)变身。

    狼人的生活并不容易。当你是人形时,你必须避开人少的城市,而当你是狼形时,你必须避开人多的城市。对于每一次行程 $i(0 \leq i \leq Q - 1)$,都有两个阈值 $L_i$ 和 $R_i(0 \leq L_i \leq R_i \leq N - 1)$,用以表示哪些城市必须要避开。准确地说,当你是人形时,你必须避开城市 $0, 1, ... , L_i - 1$ ;而当你是狼形时,则必须避开城市 $R_i + 1, R_i + 2, ..., N - 1$。这就是说,在行程 $i$ 中,你必须在城市 $L_i, L_i + 1, ..., R_i$ 中的其中一个城市内变身。

    你的任务是,对每一次行程,判定是否有可能在满足上述限制的前提下,由城市 $S_i$ 走到城市 $E_i$。你的路线可以有任意长度。

    输入输出格式

    输入格式:

    输入的第一行包含三个正整数 $N, M, Q$,其意义见题目描述。

    接下来 $M$ 行,每行包含两个非负整数。在这 $M$ 行中,第 $j$ 行的两个非负整数分别表示 $X_{j - 1}, Y_{j - 1}$,即编号为 $j - 1$ 的道路连接的两个城市的编号。

    接下来 $Q$ 行,每行包含四个非负整数。在这 $Q$ 行中,第 $i$ 行的四个非负整数分别表示 $S_{i - 1}, E_{i - 1}, L_{i - 1}, R_{i - 1}$,即编号为 $i - 1$ 的行程的起点城市编号、终点城市编号以及两个阈值。

    输出格式:

    输出包含 $Q$ 行,每行包含一个非 $0$ 即 $1$ 的整数。第 $i$ 行的整数表示对于编号为 $i - 1$ 的行程,是否能从城市 $S_{i - 1}$ 走至城市 $E_{i - 1}$,若能够,那么输出整数为 $1$;若不能,那么输出整数为 $0$。

    输入输出样例

    输入样例#1: 复制
    6 6 3
    5 1
    1 2
    1 3
    3 4
    3 0
    5 2
    4 2 1 2
    4 2 2 2
    5 4 3 4
    
    输出样例#1: 复制
    1
    0
    0
    
    输入样例#2: 复制
    10 9 10
    6 7
    1 5
    8 0
    2 9
    9 4
    2 7
    8 5
    6 0
    3 4
    4 9 0 9
    8 1 8 9
    1 8 1 8
    8 3 5 5
    8 9 3 9
    0 1 0 2
    9 0 6 6
    1 7 1 8
    9 4 5 6
    9 5 0 9
    
    输出样例#2: 复制
    1
    1
    1
    0
    1
    1
    0
    1
    0
    1
    

    说明

    限制条件

    • $2 \leq N \leq 200, 000$
    • $N - 1 \leq M \leq 400, 000$
    • $1 \leq Q \leq 200, 000$
    • 对于每个 $0 \leq j \leq M - 1$
      • $0 \leq X_j \leq N - 1$
      • $0 \leq Y_j \leq N - 1$
      • $X_j \neq Y_j$
    • 你可以通过道路由任意一个城市去另外任意一个城市。
    • 每一对城市最多只由一条道路直接连起来。换言之,对于所有 $0 \leq j < k \leq M - 1$,都有 $(X_j, Y_j) \neq (X_k, Y_k)$ 和 $(Y_j, X_j) \neq (X_k, Y_k)$
    • 对于每个 $0 \leq i \leq Q - 1$
      • $0 \leq L_i \leq S_i \leq N - 1$
      • $0 \leq E_i \leq R_i \leq N - 1$
      • $S_i \neq E_i$
      • $L_i \leq R_i$

    子任务

    • 1.(7 分) $N \leq 100$,$M \leq 200$,$Q \leq 100$
    • 2.(8 分) $N \leq 3, 000$,$M \leq 6, 000$,$Q \leq 3, 000$
    • 3.(34 分) $M = N - 1$ 且每个城市最多与两条路相连 (所有城市是以一条直线的形式连起来)
    • 4.(51 分) 没有附加限制
    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。