5807: IOI2021 D1T2:钥匙(keys)
[Creator : ]
Description
Input
Output
Constraints
Sample 1 Input
4 5
0 1 1 2
0 1 0
0 2 0
1 2 1
1 3 0
3 1 2
Sample 1 Output
0 1 1 0
如果玩家从房间$0$开始游戏,可以执⾏以下的操作序列:
因此从房间$0$出发可以到达房间$3$。 类似地,我们可以构造出操作序列表明所有$4$个房间都是从房间$0$出发可达的,所以$p[0] = 4$。 下表展⽰了从各个房间出发可以到达的房间集合:
所有房间中$p[i]$的最小值是$2$,这可以在$i = 1$或$i = 2$处取得。所以这次函数调⽤的返回值是$[0,\ 1,\ 1,\ 0]$。
因此从房间$0$出发可以到达房间$3$。 类似地,我们可以构造出操作序列表明所有$4$个房间都是从房间$0$出发可达的,所以$p[0] = 4$。 下表展⽰了从各个房间出发可以到达的房间集合:
所有房间中$p[i]$的最小值是$2$,这可以在$i = 1$或$i = 2$处取得。所以这次函数调⽤的返回值是$[0,\ 1,\ 1,\ 0]$。
Sample 2 Input
7 10
0 1 1 2 2 1 2
0 1 0
0 2 0
1 2 1
1 3 0
2 3 0
3 4 1
3 5 2
4 5 0
4 6 2
5 6 1
Sample 2 Output
0 1 1 0 1 0 1
下表展⽰了从各个房间出发可以到达的房间集合:
所有房间中$p[i]$的最小值是$2$,这可以在$i \in \{1,\ 2,\ 4,\ 6\}$处取得。所以这次函数调⽤的返回值是$[0,\ 1,\ 1,\ 0,\ 1,\ 0,\ 1]$。
所有房间中$p[i]$的最小值是$2$,这可以在$i \in \{1,\ 2,\ 4,\ 6\}$处取得。所以这次函数调⽤的返回值是$[0,\ 1,\ 1,\ 0,\ 1,\ 0,\ 1]$。
Sample 3 Input
3 1
0 0 0
0 1 0
Sample 3 Output
0 0 1
下表展⽰了从各个房间出发可以到达的房间集合:
所有房间中$p[i]$的最小值是$1$,这可以在$i = 2$处取得。所以这次函数调⽤的返回值是$[0,\ 0,\ 1]$。
所有房间中$p[i]$的最小值是$1$,这可以在$i = 2$处取得。所以这次函数调⽤的返回值是$[0,\ 0,\ 1]$。
HINT
题目来源:IOI2021 D1T2。