22024번 - Keys 서브태스크다국어언어 제한함수 구현

Timothy the architect has designed a new escape game. In this game, there are $n$ rooms numbered from $0$ to $n - 1$. Initially, each room contains exactly one key. Each key has a type, which is an integer between $0$ and $n - 1$, inclusive. The type of the key in room $i$ ($0 \le i \le n - 1$) is $r[i]$. Note that multiple rooms may contain keys of the same type, i.e., the values $r[i]$ are not necessarily distinct.

There are also $m$ bidirectional connectors in the game, numbered from $0$ to $m - 1$. Connector $j$ ($0 \le j \le m - 1$) connects a pair of different rooms $u[j]$ and $v[j]$. A pair of rooms can be connected by multiple connectors.

The game is played by a single player who collects the keys and moves between the rooms by traversing the connectors. We say that the player traverses connector $j$ when they use this connector to move from room $u[j]$ to room $v[j]$, or vice versa. The player can only traverse connector $j$ if they have collected a key of type $c[j]$ before.

At any point during the game, the player is in some room $x$ and can perform two types of actions:

• collect the key in room $x$, whose type is $r[x]$ (unless they have collected it already),
• traverse a connector $j$, where either $u[j] = x$ or $v[j] = x$, if the player has collected a key of type $c[j]$ beforehand. Note that the player never discards a key they have collected.

The player starts the game in some room $s$ not carrying any keys. A room $t$ is reachable from a room $s$, if the player who starts the game in room $s$ can perform some sequence of actions described above, and reach room $t$.

For each room $i$ ($0 \le i \le n - 1$), denote the number of rooms reachable from room $i$ as $p[i]$. Timothy would like to know the set of indices $i$ that attain the minimum value of $p[i]$ across $0 \le i \le n - 1$.

You are to implement the following procedure:

int[] find_reachable(int[] r, int[] u, int[] v, int[] c)

• $r$: an array of length $n$. For each $i$ ($0 \le i \le n - 1$), the key in room $i$ is of type $r[i]$.
• $u$, $v$: two arrays of length $m$. For each $j$ ($0 \le j \le m - 1$), connector $j$ connects rooms $u[j]$ and $v[j]$.
• $c$: an array of length $m$. For each $j$ ($0 \le j \le m - 1$), the type of key needed to traverse connector $j$ is $c[j]$.
• This procedure should return an array $a$ of length $n$. For each $0 \le i \le n - 1$, the value of $a[i]$ should be $1$ if for every $j$ such that $0 \le j \le n - 1$, $p[i] \le p[j]$. Otherwise, the value of $a[i]$ should be $0$.

Consider the following call:

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 in room $0$, they can perform the following sequence of actions:

Hence room $3$ is reachable from room $0$. Similarly, we can construct sequences showing that all rooms are reachable from room $0$, which implies $p[0] = 4$. The table below shows the reachable rooms for all starting rooms:

The smallest value of $p[i]$ across all rooms is $2$, and this is attained for $i = 1$ or $i = 2$. Therefore, this procedure should return $[0, 1, 1, 0]$.

find_reachable([0, 1, 1, 2, 2, 1, 2],
               [0, 0, 1, 1, 2, 3, 3, 4, 4, 5],
               [1, 2, 2, 3, 3, 4, 5, 5, 6, 6],
               [0, 0, 1, 0, 0, 1, 2, 0, 2, 1])

The table below shows the reachable rooms:

The smallest value of $p[i]$ across all rooms is $2$, and this is attained for $i \in \{1, 2, 4, 6\}$. Therefore, this procedure should return $[0, 1, 1, 0, 1, 0, 1]$.

find_reachable([0, 0, 0], [0], [1], [0])

The table below shows the reachable rooms:

The smallest value of $p[i]$ across all rooms is $1$, and this is attained when $i = 2$. Therefore, this procedure should return $[0, 0, 1]$.

• $2 \le n \le 300\,000$
• $1 \le m \le 300\,000$
• $0 \le r[i] \le n - 1$ for all $0 \le i \le n - 1$
• $0 \le u[j], v[j] \le n - 1$ and $u[j] \ne v[j]$ for all $0 \le j \le m - 1$
• $0 \le c[j] \le n - 1$ for all $0 \le j \le m - 1$

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 \le j \le m - 1$): $u[j]$ $v[j]$ $c[j]$

The sample grader prints the return value of find_reachable in the following format:

• line 1: $a[0]$ $a[1]$ $\cdots$ $a[n - 1]$

• keys.zip