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ドル$.

예제 1

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

예제 2

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

예제 3

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