DMOPC '20 Contest 6 P3 - Bread Merchant

View as PDF

Submit solution

Points: 10 (partial)
Time limit: 2.0s
Memory limit: 256M

Problem types

There was once a travelling merchant who traded bread by travelling on M routes between N cities, with the j-th route leading from city a_j to b_j, in only that direction. Unfortunately, one day the merchant was robbed of their fortune of bread money. Furious, the local police decided to give chase and catch the robber.

To avoid getting caught, the robber wants to repeatedly travel along the routes between cities. In fact, as long as they are at a city with at least one outgoing route, they will always travel along one of the outgoing routes to the city it leads to. If they ever reach a city with no outgoing routes, they will be cornered and caught by the police.

Furthermore, some cities have police stations (p_i = 1 if there is a police station in city i, and p_i = 0 otherwise). In cities with a police station, the police can choose an outgoing route (if one exists) and force the robber to take it. For cities without a police station, the robber can freely choose any route leading from that city. Police stations have no other effects on how the robber is caught.

For each of the N cities where the robber could have started from, determine if the police will eventually catch the robber, assuming both the police and robber act optimally.


1 \le N \le 5 \times 10^5

0 \le M \le 5 \times 10^5

p_i \in \{0, 1\}

1 \le a_j, b_j \le N

Subtask 1 [30%]

a_j \le b_j for all j.

Subtask 2 [15%]

p_i = 0 for all i.

Subtask 3 [15%]

p_i = 1 for all i.

Subtask 4 [20%]

1 \le N \le 2 \times 10^3

0 \le M \le 2 \times 10^3

Subtask 5 [20%]

No additional constraints.

Input Specification

The first line contains 2 integers N and M.

The next line contains N integers p_i (1 \le i \le N).

The next M lines each contain 2 integers a_j and b_j. Note that a_j and b_j are not necessarily distinct.

Output Specification

On a single line, output N space-separated integers, where the i-th is the answer if the robber were to start at city i. The answer is 1 if the robber will be caught and 0 otherwise.

Sample Input

5 7
1 0 1 0 1
1 2
2 1
2 3
3 2
1 4
2 4
5 5

Sample Output

1 0 0 1 0


If the robber started at city 1, then the police can force them to city 4 where they are caught.

If the robber started at either of city 2 or 3, then they can avoid being caught by always heading to city 3 when they are at city 2.

If the robber started at city 4, then they are caught immediately.

If the robber started at city 5, then the police can only force them to keep taking the route from city 5 back to city 5 itself, and this does not fall under the definition of being caught.


There are no comments at the moment.