P8519 [IOI 2021] 钥匙

# 滥用本题评测将被封号 ### 由于技术限制，请不要使用 C++ 14 (GCC 9) 提交本题。 这是一道交互题，你只需要实现代码中要求的函数。 你的代码不需要引用任何额外的头文件，也不需要实现 `main` 函数。

建筑师 Timothy 设计了一个新的密室逃脱游戏。 这个游戏里有 $n$ 个房间，房间从 $0$ 到 $n - 1$ 编号。最开始的时候，每个房间里都恰好有一把钥匙。每把钥匙都有一个类型，钥匙的类型是一个 $0$ 到 $n - 1$ 区间内的整数。第 $i$ 个房间里的钥匙类型是 $r[i]$。注意多个房间里可能会包含相同类型的钥匙，即$r[i]$ 的值不一定是两两不同的。 游戏里还有 $m$ 条**双向**的通道，通道从 $0$ 到 $m - 1$ 编号。第 $j$ 条通道连接了一对编号不同的房间 $u[j]$ 和 $v[j]$。同一对房间之间可能存在多条通道。 参与游戏的玩家需要收集钥匙和在不同的房间之间通过通道进行移动。 当玩家使用通道 $j$ 从房间 $u[j]$ 移动到 $v[j]$ ，或者反过来从 $v[j]$ 移动到 $u[j]$ 时，我们说玩家**通过**了通道 $j$。 只有当玩家收集到类型为 $c[j]$ 的钥匙时，玩家才可以通过通道 $j$。 在游戏的任意时刻，玩家可以在某个房间 $x$ 里执行以下两种操作： - 收集房间 $x$ 里面的钥匙，钥匙的类型是 $r[x]$（除⾮对应类型的钥匙已经被收集过）。 - 通过通道 $j$，需要满足 $u[j] = x$ 或 $v[j] = x$，且玩家已经获得 $c[j]$ 类型的钥匙。 注意玩家收集过的钥匙可以一直使用，**永远不会被丢弃**。 最初玩家会在某个房间 $s$ **开始**游戏，不带任何钥匙。 如果玩家从房间 $s$ 开始，通过一系列上述描述的两种操作，能够到达房间 $t$，那么称房间 $t$ 是**从房间 $s$ 开始可以到达的**。 对于每一个房间 $i ~ ( 0 \le i \le n − 1)$，定义从房间 $i$ 出发能够到达的房间数为 $p[i]$。Timothy 想要知道满⾜ $p[i]$ 值最小的下标 $i$ 的集合。

你要实现以下函数： ```cpp std::vector find_reachable( std::vector r, std::vector u, std::vector v, std::vector c ) ``` - $r$：⼀个⻓度为 $n$ 的序列。对于每⼀个 $i ~ ( 0 \leq i \leq n − 1)$，第 $i$ 个房间⾥的钥匙类型是 $r[i]$。 - $u, v$：两个⻓度为 $m$ 的序列。 对于每⼀个 $j ~ ( 0 \leq j \leq m − 1)$，第 $j$ 条通道连接了房间 $u[j]$ 和 $v[j]$。 - $c$：⼀个⻓度为 $m$ 的序列。对于每⼀个 $j ~ ( 0 \leq j \leq m − 1)$，通过通道 $j$ 需要⽤到的钥匙类型是 $c[j]$.

- 这个函数应该返回⼀个⻓度为 $n$ 的序列 $a$。对于 $0 \leq i \leq n − 1$ 中的 $i$，如果满⾜ $p[i] \leq p[j] ~ (0 \leq j \leq n − 1)$ 那么 $a[i]$ 的值为 $1$，否则 $a[i]$ 的值为 $0$。

**样例解释** 对于例 $1$，考虑以下调用： ```cpp find_reachable([0, 1, 1, 2], [0, 0, 1, 1, 3], [1, 2, 2, 3, 1], [0, 0, 1, 0, 2]) ``` 如果玩家从房间 $0$ 开始游戏，可以执⾏以下的操作序列： | 当前房间 | 操作 | | :----------: | :----------: | | $0$ | 收集钥匙类型 $0$ | | $0$ | 通过通道 $0$ 到房间 $1$ | | $1$ | 收集钥匙类型 $1$ | | $1$ | 通过通道 $2$ 到房间 $2$ | | $2$ | 通过通道 $2$ 到房间 $1$ | | $1$ | 通过通道 $3$ 到房间 $3$ | 因此从房间 $0$ 出发可以到达房间 $3$。 类似地，我们可以构造出操作序列表明所有 $4$ 个房间都是从房间 $0$ 出发可达的，所以 $p[0] = 4$。 下表展⽰了从各个房间出发可以到达的房间集合： | 开始房间 $i$ | 可以到达的房间 | $p[i]$ | | :----------: | :------------: | :----: | | $0$ | $[0, 1, 2, 3]$ | $4$ | | $1$ | $[1, 2]$ | $2$ | | $2$ | $[1, 2]$ | $2$ | | $3$ | $[1, 2, 3]$ | $3$ | 所有房间中 $p[i]$ 的最小值是 $2$，这可以在 $i = 1$ 或 $i = 2$ 处取得。所以这次函数调⽤的返回值是 $[0, 1, 1, 0]$。 对于例 $2$：所有房间中 $p[i]$ 的最小值是 $2$，这可以在 $i \in \{1, 2, 4, 6\}$ 处取得。所以这次函数调⽤的返回值是 $[0, 1, 1, 0, 1, 0, 1]$。 对于例 $3$：所有房间中 $p[i]$ 的最小值是 $1$，这可以在 $i = 2$ 处取得。所以这次函数调⽤的返回值是 $[0, 0, 1]$。 **约束条件** - $2 \leq n \leq 3 \times 10 ^ 5$ - $1 \leq m \leq 3 \times 10 ^ 5$ - $0 \leq r[i] \leq n - 1$ （对于所有的 $0 \leq i \leq n - 1$） - $0 \leq u[j], v[j] \leq n - 1$ 且 $u[j] \neq v[j]$ （对于所有的 $0 \leq j \leq m - 1$） - $0 \leq c[j] \leq n - 1$（对于所有的 $0 \leq j \leq m - 1$） **子任务** 1. （$9$ 分） $c[j] = 0$（对于所有的 $0 \leq j \leq m − 1$）且 $n, m \leq 200$ 2. （$11$ 分） $n, m \leq 20$ 3. （$17$ 分） $n, m \leq 2000$ 4. （$30$ 分） $c[j] \leq 29$（对于所有的 $0 \leq j \leq m − 1$）且 $r[i] \leq 29$（对于所有的 $0 \leq i \leq n − 1$） 5. （$33$ 分）没有额外的约束条件。 **样例评分程序** 评测程序⽰例以如下格式读取输⼊数据： - 第 $1$ ⾏：$n ~ m$ - 第 $2$ ⾏： $r[0] ~ r[1] ~ \cdots ~ r[n − 1]$ - 第 $3 + j$ ⾏ $( 0 \leq j \leq m − 1)$： $u[j] ~ v[j] ~ c[j]$ 样例评分程序按照以下格式打印 `find_reachable` 函数的返回值： 第 $1$ ⾏： $s[0] ~ s[1] \cdots ~ s[n − 1]$