P8519 [IOI 2021] Keys

### Due to technical limitations, please do not use C++14 (GCC 9) to submit this problem. This is an interactive problem. You only need to implement the function required in the code. Your code does not need to include any extra header files, and you do not need to implement the `main` function.

Architect Timothy designed a new escape-room game. In this game, there are $n$ rooms, numbered from $0$ to $n - 1$. At the beginning, each room contains exactly one key. Each key has a type, and the type is an integer in the range $0$ to $n - 1$. The key in room $i$ has type $r[i]$. Note that multiple rooms may contain keys of the same type, so the values $r[i]$ are not necessarily pairwise distinct. The game also has $m$ **undirected** corridors, numbered from $0$ to $m - 1$. Corridor $j$ connects two different rooms $u[j]$ and $v[j]$. There may be multiple corridors between the same pair of rooms. Players need to collect keys and move between rooms through corridors. When a player uses corridor $j$ to move from room $u[j]$ to room $v[j]$, or from room $v[j]$ to room $u[j]$, we say the player **passes through** corridor $j$. A player can pass through corridor $j$ only if the player has collected a key of type $c[j]$. At any time, when the player is in some room $x$, the player can perform the following two operations: - Collect the key in room $x$, whose type is $r[x]$ (unless a key of that type has already been collected). - Pass through corridor $j$, where $u[j] = x$ or $v[j] = x$, and the player has already obtained a key of type $c[j]$. Note that any key the player has collected can be used forever and is **never discarded**. Initially, the player **starts** the game in some room $s$, with no keys. If the player starts from room $s$ and can reach room $t$ by performing a sequence of the two operations described above, then room $t$ is said to be **reachable from room $s$**. For each room $i ~ ( 0 \le i \le n − 1)$, let $p[i]$ be the number of rooms that can be reached starting from room $i$. Timothy wants to know the set of indices $i$ for which $p[i]$ is minimal.

You need to implement the following function: ```cpp std::vector find_reachable( std::vector r, std::vector u, std::vector v, std::vector c ) ``` - $r$: a sequence of length $n$. For each $i ~ ( 0 \leq i \leq n − 1)$, the key type in room $i$ is $r[i]$. - $u, v$: two sequences of length $m$. For each $j ~ ( 0 \leq j \leq m − 1)$, corridor $j$ connects rooms $u[j]$ and $v[j]$. - $c$: a sequence of length $m$. For each $j ~ ( 0 \leq j \leq m − 1)$, passing through corridor $j$ requires a key of type $c[j]$.

- The function should return a sequence $a$ of length $n$. For $i$ in $0 \leq i \leq n − 1$, if $p[i] \leq p[j] ~ (0 \leq j \leq n − 1)$, then $a[i] = 1$; otherwise, $a[i] = 0$.

**Sample Explanation** For Example $1$, consider the following call: ```cpp find_reachable([0, 1, 1, 2], [0, 0, 1, 1, 3], [1, 2, 2, 3, 1], [0, 0, 1, 0, 2]) ``` If the player starts the game from room $0$, they can perform the following sequence of operations: | Current Room | Operation | | :----------: | :----------: | | $0$ | Collect key of type $0$ | | $0$ | Pass through corridor $0$ to room $1$ | | $1$ | Collect key of type $1$ | | $1$ | Pass through corridor $2$ to room $2$ | | $2$ | Pass through corridor $2$ to room $1$ | | $1$ | Pass through corridor $3$ to room $3$ | Therefore, room $3$ is reachable starting from room $0$. Similarly, we can construct operation sequences showing that all $4$ rooms are reachable from room $0$, so $p[0] = 4$. The table below shows the set of reachable rooms starting from each room: | Start Room $i$ | Reachable Rooms | $p[i]$ | | :----------: | :------------: | :----: | | $0$ | $[0, 1, 2, 3]$ | $4$ | | $1$ | $[1, 2]$ | $2$ | | $2$ | $[1, 2]$ | $2$ | | $3$ | $[1, 2, 3]$ | $3$ | The minimum value of $p[i]$ among all rooms is $2$, which is achieved at $i = 1$ or $i = 2$. Therefore, the return value of this function call is $[0, 1, 1, 0]$. For Example $2$: the minimum value of $p[i]$ among all rooms is $2$, which is achieved at $i \in \{1, 2, 4, 6\}$. Therefore, the return value of this function call is $[0, 1, 1, 0, 1, 0, 1]$. For Example $3$: the minimum value of $p[i]$ among all rooms is $1$, which is achieved at $i = 2$. Therefore, the return value of this function call is $[0, 0, 1]$. **Constraints** - $2 \leq n \leq 3 \times 10 ^ 5$. - $1 \leq m \leq 3 \times 10 ^ 5$. - $0 \leq r[i] \leq n - 1$ (for all $0 \leq i \leq n - 1$). - $0 \leq u[j], v[j] \leq n - 1$ and $u[j] \neq v[j]$ (for all $0 \leq j \leq m - 1$). - $0 \leq c[j] \leq n - 1$ (for all $0 \leq j \leq m - 1$). **Subtasks** 1. ($9$ points) $c[j] = 0$ (for all $0 \leq j \leq m − 1$) and $n, m \leq 200$. 2. ($11$ points) $n, m \leq 20$. 3. ($17$ points) $n, m \leq 2000$. 4. ($30$ points) $c[j] \leq 29$ (for all $0 \leq j \leq m − 1$) and $r[i] \leq 29$ (for all $0 \leq i \leq n − 1$). 5. ($33$ points) No additional constraints. **Sample Grader** The sample grader reads the input in the following format: - Line $1$: $n ~ m$. - Line $2$: $r[0] ~ r[1] ~ \cdots ~ r[n − 1]$. - Line $3 + j$ $( 0 \leq j \leq m − 1)$: $u[j] ~ v[j] ~ c[j]$. The sample grader prints the return value of the `find_reachable` function in the following format: - Line $1$: $s[0] ~ s[1] \cdots ~ s[n − 1]$. Translated by ChatGPT 5