|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|2 초||512 MB||7||7||7||100.000%|
Arezou and her brother Borzou are twins. They have received an amazing toy train set for their birthday, and they used it to build a railway system with $n$ stations and $m$ one-way tracks. The stations are numbered from $0$ to $n-1$. Each track starts at one station and ends at the same or a different station. There is at least one track starting at each station.
Some stations are charging stations. Whenever the train arrives at a charging station, it gets fully charged. A fully charged train has enough energy to travel along $n$ consecutive tracks. That is, the train runs out of energy just when it enters the $(n+1)$-st track after last being charged.
On each station there is a switch that can be pointed to any of the tracks that start at that station. When a train is at a station, it leaves it using the track that is pointed to by the switch on that station.
The twins are going to play a game with their train. They have already divided all the stations between themselves: each station is either owned by Arezou or by Borzou. There is a single train. At the beginning of the game the train is at station $s$ and it is fully charged. To start the game, the owner of station $s$ points the switch on station $s$ to one of the tracks that start at station $s$. Then, they turn the train on and the train starts traveling along the tracks.
Whenever the train enters a station for the first time, the owner of that station sets the switch on that station. Once a switch is set, it stays in the same position for the rest of the game. Thus, if a train re-enters a station it visited before, it will leave that station along the same track as before.
Since there is a finite number of stations, the train will eventually start going along a cycle. A cycle is a sequence of distinctstations $c, c, \cdots, c[k-1]$ such that the train leaves station $c[i]$ (for $0 \leq i < k-1$) using a track going to station $c[i+1]$, and it leaves station $c[k-1]$ using a track going to station $c$. Note that a cycle may consist of a single station (i.e., have $k=1$) if the train leaves the station $c$ using a track that goes back to $c$.
Arezou wins the game if the train continues going indefinitely, and Borzou wins if the train runs out of energy. In other words, if there is at least one charging station among $c, c, \cdots, c[k-1]$, the train can recharge and cycle indefinitely, and Arezou wins. Otherwise, it will run out of energy (possibly after turning around the cycle several times), and Borzou wins.
You are given the description of the railway system. Arezou and Borzou are going to play $n$ games. In the $s$-th game, for $0 \leq s \leq n-1$, the train will initially be at station $s$. Your task is to find, for each game, whether there is a strategy for Arezou that guarantees she wins, regardless of how Borzou plays.
You should implement the following procedure:
int who_wins(int a, int r, int u, int v)
who_wins([0, 1], [1, 0], [0, 0, 1, 1], [0, 1, 0, 1])
For all $0 \leq i \leq m-1$, either $v[i] = u[i]$ or $v[i] = u[i] + 1$.
$n \leq 15$.
Arezou owns all stations.
Borzou owns all stations.
There is exactly one charging station.
No additional constraints.
The sample grader reads the input in the following format:
The sample grader prints the return value of
who_wins in the following format:
C++17, C++14, C++20, C++14 (Clang), C++17 (Clang), C++20 (Clang)