#P18787. [KOI2026 二轮] 游戏
[KOI2026 二轮] 游戏
[KOI2026 二轮] 游戏(게임 / Game)
题目描述
Alice 和 Bob 在一座迷宫中玩游戏。迷宫有 个房间,编号为 到 。若 ,房间 有出口;若 ,则没有。
迷宫中有 种双向通道。第 种连接房间 ,共有 条彼此不同的通道。不同种类对应不同的无序房间对。迷宫不一定连通。
两人独立进行 局游戏。第 局从房间 开始,并固定使用正整数 。每次移动按以下规则进行:
- Alice 从当前房间相连的通道中,选择恰好 条不同通道。可以同时选择多条通往同一房间的通道。若通道总数不足 ,则无法移动。
- Bob 从这些被选中的通道中选出一条,Alice 沿该通道到达另一端的房间。
Alice 的目标是经过零次或多次移动,到达任意一个有出口的房间。起点有出口时立即获胜。Bob 则尽力阻止她到达出口;无限移动而始终无法到达出口也不算 Alice 获胜。
对每局游戏,判断 Alice 是否有一个策略,使她无论 Bob 如何选择,都能在有限次移动后到达出口。
输入格式
第一行三个整数 。
第二行 个整数 。
接下来 行,每行三个整数 。
接下来 行,每行两个整数 ,表示一局独立游戏。
输出格式
输出 行。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
房间 是唯一出口。第二局中,Alice 在房间 可以各选一条通往 的通道;若到达 ,再选择两条通往 的通道即可。第四局起点 只有三条通道,无法选择四条;第五局的起点 是无出口的孤立点。
样例 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 陷入无法移动的房间 ,或在房间 之间循环,从而阻止到达房间 。
样例 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 | 6 | ,,且只有房间 有出口 |
| 2 | 8 | , |
| 3 | 7 | 所有 |
| 4 | 14 | 所有 相等 |
| 5 | 15 | 所有 相等 |
| 6 | 16 | ,所有 |
| 7 | 34 | 无附加限制 |
满分 100 分。时限 3 秒,内存 1024 MiB。