Reindeer Games
Contest: Codeforces Global Round 18
Difficulty rating: 3000
Tags: binary search, constructive algorithms, data structures, divide and conquer, flows, graphs, shortest paths

There are $$$n$$$ reindeer at the North Pole, all battling for the highest spot on the "Top Reindeer" leaderboard on the front page of CodeNorses (a popular competitive reindeer gaming website). Interestingly, the "Top Reindeer" title is just a measure of upvotes and has nothing to do with their skill level in the reindeer games, but they still give it the utmost importance.

Currently, the $$$i$$$-th reindeer has a score of $$$a_i$$$. You would like to influence the leaderboard with some operations. In an operation, you can choose a reindeer, and either increase or decrease his score by $$$1$$$ unit. Negative scores are allowed.

You have $$$m$$$ requirements for the resulting scores. Each requirement is given by an ordered pair $$$(u, v)$$$, meaning that after all operations, the score of reindeer $$$u$$$ must be less than or equal to the score of reindeer $$$v$$$.

Your task is to perform the minimum number of operations so that all requirements will be satisfied.

Input format:
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$2\le n\le 1000$$$; $$$1\le m\le 1000$$$) — the number of reindeer and requirements, respectively.

The second line contains $$$n$$$ integers $$$a_1,\ldots, a_n$$$ ($$$1\le a_i\le 10^9$$$), where $$$a_i$$$ is the current score of reindeer $$$i$$$.

The next $$$m$$$ lines describe the requirements.

The $$$i$$$-th of these lines contains two integers $$$u_i$$$ and $$$v_i$$$ ($$$1\le u_i, v_i\le n$$$; $$$u_i\ne v_i$$$) — the two reindeer of the $$$i$$$-th requirement.

Output format:
Print $$$n$$$ integers $$$b_1,\ldots, b_n$$$ ($$$-10^{15}\le b_i\le 10^{15}$$$), where $$$b_i$$$ is the score of the $$$i$$$-th reindeer after all operations.

If there are multiple solutions achieving the minimum number of operations, you may output any.

We can prove that there is always an optimal solution such that $$$|b_i|\le 10^{15}$$$ for all $$$i$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Example input:
7 6
3 1 4 9 2 5 6
1 2
2 3
3 4
4 5
5 6
6 7

Example output:
1 1 4 4 4 5 6

Example input:
4 6
6 5 8 2
3 1
4 1
3 2
1 2
2 3
3 1

Example output:
6 6 6 2

Editorial:
Let's try to find a nice lower bound for the answer. Let's denote a requirement of two nodes $$$u$$$ and $$$v$$$ by a directed edge $$$u\to v$$$. We can observe that if there are two nodes $$$u$$$ and $$$v$$$ such that there's a requirement $$$u\to v$$$ (or a path of requirements from $$$u$$$ to $$$v$$$), then we will need to do at least $$$a_u-a_v$$$ operations on these two nodes. So, if we can create a list of pairs $$$(u_1,v_1),\ldots, (u_k,v_k)$$$ with all distinct nodes such that there is a path from $$$u_i$$$ to $$$v_i$$$ for all $$$i$$$, then a lower bound of the answer is $$$$$$\sum\limits_{i=1}^k (a_{u_i}-a_{v_i})$$$$$$
Our strategy will be to find the largest possible lower bound of this form, and then construct a solution with exactly that cost (which is therefore the optimal cost). To find an optimal set of pairs, we can set it up as a flow problem. Every directed edge $$$u\to v$$$ of the original graph will have infinite capacity and a cost of $$$a_u-a_v$$$. In addition, we will create two new nodes $$$s$$$ and $$$t$$$. For each node $$$u$$$, add an edge $$$s\to u$$$ with capacity $$$1$$$ and cost $$$0$$$, and add an edge $$$u\to t$$$ with capacity $$$1$$$ and cost $$$0$$$.
Compute the maximum cost flow from $$$s$$$ to $$$t$$$ (the amount of flow doesn't need to be maximized). If there is any node $$$u$$$ such that $$$s\to u$$$ and $$$u\to t$$$ both have flow, make them both have $$$0$$$ flow, and this won't change the cost. The flow can be decomposed into paths with distinct endpoints in the original graph. The endpoints are distinct because each node $$$u$$$ cannot have flow on both edges $$$s\to u$$$ and $$$u\to t$$$. And the cost of a path beginning in $$$u$$$ and ending in $$$v$$$ will be $$$a_u-a_v$$$ (intermediate nodes of the path cancel out when computing the cost). It's also easy to see that any set of pairs has a corresponding flow in the graph with the same cost. So, this flow gives us a way to compute a set of pairs with the maximum lower bound, just like we want.
Now, how do we construct the operations to perform? First, take the edges of the residual flow graph that are not at full capacity. Using only these edges, compute the longest path from $$$s$$$ to every node in the graph (where length of a path is the sum of edge costs). Let's say the longest path from $$$s$$$ to $$$u$$$ is $$$d_u$$$.
Let's show that $$$b_u:=a_u+d_u$$$ satisfies all requirements. Every requirement $$$u\to v$$$ is present in the residual graph because it has infinite capacity. So we have that $$$d_u+(a_u-a_v)\le d_v$$$, otherwise we could find a longer path from $$$s$$$ to $$$v$$$. By moving $$$a_v$$$ to the right side of this inequality, we get $$$a_u+d_u\le a_v+d_v$$$, In other words, $$$b_u\le b_v$$$, meaning this requirement is satisfied.
Let's show that the total number of operations $$$\sum_u|b_u-a_u|$$$ does not exceed the cost of the flow. It's sufficient to show that for each node $$$u$$$ that isn't in one of the pairs, we have $$$b_u=a_u$$$, and for each pair $$$(u_i, v_i)$$$ we have that $$$a_{v_i}\le b_{v_i}=b_{u_i}\le a_{u_i}$$$.
For the first part, suppose a node $$$u$$$ is unpaired. If $$$d_u>0$$$, then there is a path from $$$s$$$ to $$$u$$$ with positive cost, and there is an edge from $$$u$$$ to $$$t$$$ of $$$0$$$ cost because it's unpaired, so we've found an augmenting path in the flow graph that will increase the cost. This contradicts the fact that we found the maximum cost flow. On the other hand, if $$$d_u<0$$$, this contradicts the definition of $$$d_u$$$ since there's an edge $$$s\to u$$$ of cost $$$0$$$ which makes a longer path. Therefore, $$$d_u=0$$$ and $$$b_u=a_u+d_u=a_u$$$, as desired.
For the second part, consider a pair $$$(u_i,v_i)$$$. There is a path in the residual graph from $$$v_i$$$ to $$$u_i$$$, so we have $$$d_{v_i}+(a_{v_i}-a_{u_i})\le d_{u_i}$$$. In other words, $$$b_{v_i}\le b_{u_i}$$$. But we already had that $$$b_{u_i}\le b_{v_i}$$$ because all requirements are satisfied, therefore $$$b_{u_i}=b_{v_i}$$$. It's impossible to have $$$d_{v_i}<0$$$ because there's a longer path with the direct edge $$$s\to v_i$$$ which is present in the residual graph. It's impossible to have $$$d_{u_i}>0$$$ because it would mean the edge $$$u_i\to t$$$ creates an augmenting path with positive cost. Therefore, $$$a_{v_i}\le a_{v_i}+d_{v_i}=b_{v_i}=b_{u_i}=a_{u_i}+d_{u_i}\le a_{u_i}$$$, as desired.
In summary, the solution is to build a flow graph, compute the maximum cost flow (which is equivalent to minimum cost flow with all costs negated), and compute the distance values $$$d_u$$$ to construct the solution. The flow can be computed with the potential method in $$$O(nm\log n)$$$ time.