Problem5807--IOI2021 D1T2:钥匙(keys)

5807: IOI2021 D1T2:钥匙(keys)

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 256 MiB

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]$。

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]$。

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]$。

HINT

题目来源:IOI2021 D1T2。

Source/Category