IOI '18 P3 - Werewolf - DMOJ: Modern Online Judge

IOI '18 P3 - Werewolf

Points: 30 (partial)

Time limit: 1.8s

Memory limit: 512M

Problem type

Allowed languages

C++

There are $N$ $N$ cities and $M$ $M$ roads in Ibaraki Prefecture, Japan. Cities are numbered from $0$ $0$ through $N-1$ $N - 1$ in the increasing order of their population. Each road connects a pair of distinct cities, and can be traveled in both directions. You can travel from any city to any other city by using one or more of these roads.

You planned $Q$ $Q$ trips, numbered from $0$ $0$ through $Q-1$ $Q - 1$ . The trip $i$ $i$ $(0 \le i \le Q-1)$ $(0 \leq i \leq Q - 1)$ is to travel from the city $S_i$ $S_{i}$ to the city $E_i$ $E_{i}$ .

You are a werewolf. You have two forms: human form and wolf form. At the beginning of each trip you are in human form. At the end of each trip, you must be in wolf form. During the trip you have to transform (change from human form to wolf form) exactly once. You can transform only when you are in some city (possibly $S_i$ $S_{i}$ or $E_i$ $E_{i}$ ).

Living as a werewolf is not easy. You must avoid low-populated cities when you are in human form, and avoid highly-populated cities when you are in wolf form. For each trip $i$ $i$ $(0 \le i \le Q-1)$ $(0 \leq i \leq Q - 1)$ , there are two thresholds $L_i$ $L_{i}$ and $R_i$ $R_{i}$ $(0 \le L_i \le R_i \le N-1)$ $(0 \leq L_{i} \leq R_{i} \leq N - 1)$ that indicate which cities must be avoided. More specifically, you must avoid the cities $0, 1, \dots, L_i-1$ $0, 1, \dots, L_{i} - 1$ when you are in human form, and must avoid the cities $R_i+1, R_i+2, \dots, N-1$ $R_{i} + 1, R_{i} + 2, \dots, N - 1$ when you are in wolf form. This means in the trip $i$ $i$ , you can only transform in one of the cities $L_i, L_i + 1, \dots, R_i$ $L_{i}, L_{i} + 1, \dots, R_{i}$ .

Your task is to determine, for each trip, whether it is possible to travel from the city $S_i$ $S_{i}$ to the city $E_i$ $E_{i}$ in a way that satisfies the aforementioned constraints. The route you take can have an arbitrary length.

Implementation details

You should implement the following function:

Copy

std::vector<int> check_validity(int N, std::vector<int> X, std::vector<int> Y, std::vector<int> S, std::vector<int> E, std::vector<int> L, std::vector<int> R)

$N$ $N$ : the number of cities.
$X$ $X$ and $Y$ $Y$ : arrays of length $M$ $M$ . For each $j$ $j$ $(0 \le j \le M-1)$ $(0 \leq j \leq M - 1)$ , the city X[j] is directly connected to the city Y[j] by a road.
$S$ $S$ , $E$ $E$ , $L$ $L$ , and $R$ $R$ : arrays of length $Q$ $Q$ , representing the trips.

Note that the values of $M$ $M$ and $Q$ $Q$ are the lengths of the arrays, and can be obtained as indicated in the implementation notice.

The function check_validity is called exactly once for each test case. This function should return an array $A$ $A$ of integers of length $Q$ $Q$ . The value of $A_i$ $A_{i}$ $(0 \le i \le Q-1)$ $(0 \leq i \leq Q - 1)$ must be $1$ $1$ if the trip $i$ $i$ is possible while satisfying the aforementioned conditions, or $0$ $0$ otherwise.

Example

Let $N = 6$ $N = 6$ , $M = 6$ $M = 6$ , $Q = 3$ $Q = 3$ , $X = [5, 1, 1, 3, 3, 5]$ $X = [5, 1, 1, 3, 3, 5]$ , $Y = [1, 2, 3, 4, 0, 2]$ $Y = [1, 2, 3, 4, 0, 2]$ , $S = [4, 4, 5]$ $S = [4, 4, 5]$ , $E = [2, 2, 4]$ $E = [2, 2, 4]$ , $L = [1, 2, 3]$ $L = [1, 2, 3]$ , $R = [2, 2, 4]$ $R = [2, 2, 4]$ .

Copy

check_validity(6, {5, 1, 1, 3, 3, 5}, {1, 2, 3, 4, 0, 2}, {4, 4, 5}, {2, 2, 4}, {1, 2, 3}, {2, 2, 4})

$\text{[math]}$

For the trip $0$ $0$ , you can travel from the city $4$ $4$ to the city $2$ $2$ as follows:

Start at city $4$ $4$ (You are in human form)
Move to the city $3$ $3$ (You are in human form)
Move to city $1$ $1$ (You are in human form)
Transform yourself into wolf form (You are in wolf form)
Move to the city $2$ $2$ (You are in wolf form)

For the trips $1$ $1$ and $2$ $2$ , you cannot travel between the given cities.

Hence, your program should return [1, 0, 0].

Constraints

$2 \le N \le 200\,000$ $2 \leq N \leq 200 000$
$N-1 \le M \le 400\,000$ $N - 1 \leq M \leq 400 000$
$1 \le Q \le 200\,000$ $1 \leq Q \leq 200 000$
For each $0 \le j \le M-1$ $0 \leq j \leq M - 1$
- $0 \le X_j \le N-1$ $0 \leq X_{j} \leq N - 1$
- $0 \le Y_j \le N-1$ $0 \leq Y_{j} \leq N - 1$
- $X_j \neq Y_j$ $X_{j} \neq Y_{j}$
You can travel from any city to any other city by using roads.
Each pair of cities are directly connected by at most one road. In other words, for all $0 \le j < k \le M-1$ $0 \leq j < k \leq M - 1$ , $(X_j, Y_j) \neq (X_k, Y_k)$ $(X_{j}, Y_{j}) \neq (X_{k}, Y_{k})$ and $(Y_j, X_j) \neq (X_k, Y_k)$ $(Y_{j}, X_{j}) \neq (X_{k}, Y_{k})$ .
For each $0 \le i \le Q-1$ $0 \leq i \leq Q - 1$
- $0 \le L_i \le S_i \le N-1$ $0 \leq L_{i} \leq S_{i} \leq N - 1$
- $0 \le E_i \le R_i \le N-1$ $0 \leq E_{i} \leq R_{i} \leq N - 1$
- $S_i \neq E_i$ $S_{i} \neq E_{i}$
- $L_i \le R_i$ $L_{i} \leq R_{i}$

Subtasks

Subtask	Points	Constraints
$1$ $1$	$7$ $7$ points	$N \le 100$ $N \leq 100$ , $M \le 200$ $M \leq 200$ , $Q \le 100$ $Q \leq 100$
$2$ $2$	$8$ $8$ points	$N \le 3\,000$ $N \leq 3 000$ , $M \le 6\,000$ $M \leq 6 000$ , $Q \le 3\,000$ $Q \leq 3 000$
$3$ $3$	$34$ $34$ points	$M = N - 1$ $M = N - 1$ and each city is incident to at most $2$ $2$ roads (the cities are connected in a line)
$4$ $4$	$51$ $51$ points	No additional constraints

Sample Grader

The sample grader reads the input in the following format:

line $1$ $1$ : $N\ M\ Q$ $N M Q$
line $2 + j$ $2 + j$ $(0 \le j \le M-1)$ $(0 \leq j \leq M - 1)$ : $X_j\ Y_j$ $X_{j} Y_{j}$
line $2 + M + i$ $2 + M + i$ $(0 \le i \le Q-1)$ $(0 \leq i \leq Q - 1)$ : $S_i\ E_i\ L_i\ R_i$ $S_{i} E_{i} L_{i} R_{i}$

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

line $1 + i$ $1 + i$ $(0 \le i \le Q-1)$ $(0 \leq i \leq Q - 1)$ : $A_i$ $A_{i}$

Comments

There are no comments at the moment.