All submissions for this problem are available.
Fluffy the squirrel lives in a big city, which contains n towns. There are m uni-directional roads in the city. ci people live in town i. For each town i, Fluffy starts at town i, and keeps moving to other towns using the uni-directional roads, for as long as he wants. Fluffy would like to maximize the number of distinct people he visits along the way. (including the inhabitants of town i) He would like to know the maximum number of people he can meet for all possible starting towns i. Can you help him?
The first line contains two space-seperated integers n, m, the number of towns and the number of roads in the city. The next line contains n space-seperated integers ci, denoting the number of people in each city. The next m lines contain two space-seperated integers, ui and vi, denoting that there is a road going from town ui to town vi.
Output n space-seperated integers, where the i-th integer denotes the maximum number of people Fluffy can visit if he is town i.
- 1 ≤ n, m ≤ 100000
- 1 ≤ ci ≤ 109
- 1 ≤ u, v ≤ n
- u and v will not be equal for all roads.
- Subtask 1 (16 points) : If there exist a road from u to v, then there exist a road from v to u.
- Subtask 2 (39 points) : For each pair of towns u, v, if you can reach v from u, then you can't reach u from v.
- Subtask 3 (45 points) : Original Constraints
Input: 7 8 1 2 3 4 5 6 7 1 2 2 3 3 4 4 5 5 2 5 6 5 7 4 7 Output: 22 21 21 21 21 6 7
Example case. Fluffy cannot go anywhere else if he's in cities 6 and 7. If he is in city 5, he can go on the path 5 -> 2 -> 3 -> 4 -> 5 -> 7, which visits 2 + 3 + 4 + 5 + 7 = 21 different people. Note that the people in town 5 is counted once despite being visited twice. A similar path exist from towns 2, 3, 4. From town 1, the path 1 -> 2 -> 3 -> 4 -> 5 -> 7 visits 22 different people.
|Tags||dynamic-programming, easy-medium, scc, zscoder|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||CPP14, JAVA, PYTH, PYTH 3.6, PYP3|
Fetching successful submissions
If you are still having problems, see a sample solution here.