#P18787. [KOI2026 二轮] 游戏

[KOI2026 二轮] 游戏

[KOI2026 二轮] 游戏(게임 / Game)

题目描述

Alice 和 Bob 在一座迷宫中玩游戏。迷宫有 NN 个房间,编号为 11 到 NN。若 Ai=1A_i=1,房间 ii 有出口;若 Ai=0A_i=0,则没有。

迷宫中有 MM 种双向通道。第 ii 种连接房间 ai,bia_i,b_i,共有 cic_i 条彼此不同的通道。不同种类对应不同的无序房间对。迷宫不一定连通。

两人独立进行 QQ 局游戏。第 jj 局从房间 sjs_j 开始,并固定使用正整数 kjk_j。每次移动按以下规则进行:

  1. Alice 从当前房间相连的通道中,选择恰好 kjk_j 条不同通道。可以同时选择多条通往同一房间的通道。若通道总数不足 kjk_j,则无法移动。
  2. Bob 从这些被选中的通道中选出一条,Alice 沿该通道到达另一端的房间。

Alice 的目标是经过零次或多次移动,到达任意一个有出口的房间。起点有出口时立即获胜。Bob 则尽力阻止她到达出口;无限移动而始终无法到达出口也不算 Alice 获胜。

对每局游戏,判断 Alice 是否有一个策略,使她无论 Bob 如何选择,都能在有限次移动后到达出口。

输入格式

第一行三个整数 N,M,QN,M,Q。

第二行 NN 个整数 A1,…,ANA_1,\ldots,A_N。

接下来 MM 行,每行三个整数 ai,bi,cia_i,b_i,c_i。

接下来 QQ 行,每行两个整数 sj,kjs_j,k_j,表示一局独立游戏。

输出格式

输出 QQ 行。Alice 能保证获胜则输出 YES,否则输出 NO。

样例 1

5 5 5
0 0 1 0 0
1 2 1
1 3 1
1 4 2
2 3 2
3 4 1
2 1
1 2
3 3
4 4
5 1
YES
YES
YES
NO
NO

房间 33 是唯一出口。第二局中,Alice 在房间 11 可以各选一条通往 2,32,3 的通道;若到达 22,再选择两条通往 33 的通道即可。第四局起点 44 只有三条通道,无法选择四条;第五局的起点 55 是无出口的孤立点。

样例 2

4 3 4
1 0 0 0
1 2 2
2 3 3
3 4 1
1 3
2 2
3 3
4 1
YES
YES
NO
YES

第三局 Bob 能使 Alice 陷入无法移动的房间 44,或在房间 2,32,3 之间循环,从而阻止到达房间 11。

样例 3

4 3 3
0 1 1 0
1 2 1
1 3 3
1 4 2
4 2
1 3
4 3
YES
YES
NO

样例 4

2 0 2
1 0
1 1
2 1
YES
NO

数据范围与子任务

  • 1≤N≤2000001\le N\le200000,0≤M≤4000000\le M\le400000,1≤Q≤2000001\le Q\le200000;
  • Ai∈{0,1}A_i\in\{0,1\};
  • 1≤ai<bi≤N1\le a_i<b_i\le N,不同通道种类的 (ai,bi)(a_i,b_i) 互不相同;
  • 1≤ci≤1091\le c_i\le10^9;
  • 1≤sj≤N1\le s_j\le N,1≤kj≤10181\le k_j\le10^{18}。

所有输入均为整数。

子任务 分值 附加限制
1 6 M=N−1M=N-1,ai=i,bi=i+1a_i=i,b_i=i+1,且只有房间 11 有出口
2 8 M=N−1M=N-1,ai=1,bi=i+1a_i=1,b_i=i+1
3 7 所有 kj=1k_j=1
4 14 所有 kjk_j 相等
5 15 所有 sjs_j 相等
6 16 N,M≤3000N,M\le3000,所有 kj≤3000k_j\le3000
7 34 无附加限制

满分 100 分。时限 3 秒,内存 1024 MiB。