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 ≤ i ≤ 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 ≤ j ≤ 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 ≤ i ≤ 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 ≤ i ≤ n − 1.

Implementation Details

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 ≤ i ≤ n − 1), the key in room i is of type r[i].
• u, v: two arrays of length m. For each j (0 ≤ j ≤ m − 1), connector j connects rooms u[j] and v[j].
• c: an array of length m. For each j (0 ≤ j ≤ 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 ≤ i ≤ n − 1, the value of a[i] should be 1 if for every j such that 0 ≤ j ≤ n − 1, p[i] ≤ p[j]. Otherwise, the value of a[i] should be 0.

Examples

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

Example 2

Consider the following call:

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 ∈ {1, 2, 4, 6}. Therefore, this procedure should return [0, 1, 1, 0, 1, 0, 1].

Example 3

Consider the following call:

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

Constraints

Do note that you DO NOT necessarily have to solve for the general case, but only for the subproblem defined by the following constraints:
* $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] \neq 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$
* $c[j] \le 29$ (for all $0 \le j \le m - 1$) and $r[i] \le 29$ (for all $0 \le i \le n - 1$)

Sample Grader

The sample grader reads the input in the following format:

• line 1: n m
• line 2: r[0] r[1] … r[n − 1]
• line 3 + j (0 ≤ j ≤ 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] … a[n − 1]

You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution, then provide a complete implementation in C++17. You should correctly implement the routine(s) described in Implementation Details, without reading or writing anything directly from stdin or to stdout, as input and output are passed through the implemented routines. Assume your code will be run on the OFFICIAL grader, and do not add a main, a sample grader, or any other functionality unless it has been explicitly requested.
Put your final solution within a single code block: cpp <your code here>

Problem statement (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 ≤ i ≤ 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 ≤ j ≤ 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 ≤ i ≤ 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 ≤ i ≤ n − 1.

Implementation Details

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 ≤ i ≤ n − 1), the key in room i is of type r[i].
• u, v: two arrays of length m. For each j (0 ≤ j ≤ m − 1), connector j connects rooms u[j] and v[j].
• c: an array of length m. For each j (0 ≤ j ≤ 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 ≤ i ≤ n − 1, the value of a[i] should be 1 if for every j such that 0 ≤ j ≤ n − 1, p[i] ≤ p[j]. Otherwise, the value of a[i] should be 0.

Examples

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

Example 2

Consider the following call:

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 ∈ {1, 2, 4, 6}. Therefore, this procedure should return [0, 1, 1, 0, 1, 0, 1].

Example 3

Consider the following call:

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

Constraints

Do note that you DO NOT necessarily have to solve for the general case, but only for the subproblem defined by the following constraints:
* $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] \neq 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$
* $c[j] \le 29$ (for all $0 \le j \le m - 1$) and $r[i] \le 29$ (for all $0 \le i \le n - 1$)

Sample Grader

The sample grader reads the input in the following format:

• line 1: n m
• line 2: r[0] r[1] … r[n − 1]
• line 3 + j (0 ≤ j ≤ 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] … a[n − 1]

Execution limits

Your solution will have 2.0 second(s) execution time and 2048 MB memory limit to solve each test case.

Starting code

Here's your starting code with some skeleton/placeholder functionality:

#include <vector>

std::vector<int> find_reachable(std::vector<int> r, std::vector<int> u, std::vector<int> v, std::vector<int> c) {
    std::vector<int> ans(r.size(), 1);

    return ans;
}

参考函数签名

#include <vector>

std::vector<int> find_reachable(std::vector<int> r, std::vector<int> u, std::vector<int> v, std::vector<int> c) {
    std::vector<int> ans(r.size(), 1);

    return ans;
}

请在 submission.cpp 中实现该函数（可 #include "problem.h" 获取题目提供的声明）。判题时你的代码会与题目提供的 grader 一起编译链接。

本题是函数题，由 grader 调用你实现的函数。

由 grader 打印判定结果，无需自行读写 stdin/stdout。

include <vector>

std::vector<int> find_reachable(std::vector<int> r, std::vector<int> u, std::vector<int> v, std::vector<int> c) {
std::vector<int> ans(r.size(), 1);

return ans;

}