Arezou's Infinite Train

Arezou and her twin brother Borzou received a set of toy trains as a birthday gift. They used the trains to build a railway system consisting of \(n\) stations (numbered from \(0\) to \(n-1\)) and \(m\) directed tracks. Each track starts at some station and ends at the same or a different station. Every station has at least one outgoing track. Additionally, some stations are charging stations. Whenever the train arrives at a charging station, its battery is recharged to full. A full battery is enough to traverse \(n\) tracks consecutively; however, if the train does not get recharged soon enough, it will run out of battery just as it is about to traverse the \((n+1)\)th track.

Each station is equipped with a switch that can be set to point to any one of the outgoing tracks from that station. When the train departs a station, it will follow the track indicated by the switch. The stations have been divided between the two players: each station belongs either to Arezou or to Borzou. The game uses a single train. At the start of the game the train is parked at station \(s\) with a full battery. To initiate the game, the owner of station \(s\) sets the switch at station \(s\) to point to one of the outgoing tracks. Then the train is started and begins to follow the tracks. Whenever the train enters a station for the first time, the owner of that station must set the switch there. Once set, that switch remains unchanged for the rest of the game. Hence, if the train visits a station more than once, it will leave along the track chosen the first time.

Since there are only finitely many stations, the train’s journey eventually falls into a cycle. A cycle is defined as a sequence of distinct stations \(c_0, c_1, \dots, c_{k-1}\) such that after leaving \(c_i\) (for \(0 \le i < k-1\)) the train takes the track leading to \(c_{i+1}\) and after leaving \(c_{k-1}\) it takes the track leading back to \(c_0\). A cycle may consist of a single station \(c_0\) (i.e. \(k=1\)) if the only outgoing track from \(c_0\) goes back to itself.

If the train is able to run forever, Arezou wins; otherwise, if it eventually runs out of battery and stops, Borzou wins. More precisely, if the cycle \(c_0, c_1, \dots, c_{k-1}\) contains at least one charging station (so that the train can continue to recharge indefinitely), then Arezou wins. Otherwise, even if the train traverses the cycle several times, it will eventually run out of battery and Borzou wins.

Given a railway system, Arezou and Borzou play \(n\) rounds of the game. In the \(s\)-th round (\(0 \le s \le n-1\)) the train starts at station \(s\) (with a full battery). Your task is to determine, for each game, whether Arezou can force a win regardless of how Borzou plays.

Battery Mechanics

The train starts with a full battery (which can cover \(n\) tracks). When the train arrives at a station with a charging facility, its battery is recharged to full. Otherwise, each track traversed decreases the remaining battery by 1. If the battery would be insufficient to traverse the next track (i.e. it would drop to 0), the train stops and Borzou wins (unless a charging station is encountered in time to reset the battery).

Input Function

You are required to implement the following function:

• std::vector<int> who_wins(std::vector<int> a, std::vector<int> r, std::vector<int> u, std::vector<int> v) in C++
• int[] who_wins(int[] a, int[] r, int[] u, int[] v) in Java

Here:

• a is an array of length \(n\) where \(a_i = 1\) if station \(i\) is owned by Arezou, and \(a_i = 0\) if it is owned by Borzou.
• r is an array of length \(n\) where \(r[i] = 1\) if station \(i\) is a charging station, and \(r[i] = 0\) otherwise.
• u and v are arrays of length \(m\). For each \(0 \le i \le m-1\), there is a directed track from station \(u_i\) to station \(v_i\).

The function should return an array \(w\) of length \(n\), where \(w_i = 1\) if Arezou can force a win when the train starts at station \(i\), regardless of how Borzou plays, and \(w_i = 0\) otherwise.

inputFormat

The input consists of four arrays:

• An integer array a of length \(n\), where \(a[i] = 1\) if station \(i\) is owned by Arezou, and 0 otherwise.
• An integer array r of length \(n\), where \(r[i] = 1\) if station \(i\) is a charging station, and 0 otherwise.
• Two integer arrays u and v each of length \(m\). For each index \(i\), there is a directed track from station u[i] to station v[i].

It is guaranteed that every station has at least one outgoing track.

outputFormat

Return an integer array w of length \(n\). For every \(0 \le i \le n-1\), w[i] = 1 if, when the train starts at station \(i\) with a full battery, Arezou can force a win regardless of Borzou's moves; otherwise, w[i] = 0.

sample

a = [1, 0, 1]
r = [0, 1, 0]
u = [0, 1, 2]
v = [1, 2, 0]

[1, 1, 1]