Editorial for DMOPC '20 Contest 2 P3 - Roadrollification - Olympiads Online Judge

Editorial for DMOPC '20 Contest 2 P3 - Roadrollification

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: richardzhang

Subtask 1

Bruteforce the answer by trying every edge and doing graph traversals or topological sorts to see if roadrollifying that edge yields the best answer.

Time complexity: $\mathcal O(N^2)$ $O (N^{2})$

Subtask 2

Perform two topological sorts: one directed along the given edge directions, and one with reversed edge directions. During the topological sorts, keep track of how many people are able to enter into this node from any other node (i.e. for any node $v$ $v$ that the current node $u$ $u$ can access, do $\mathrm{people}[v] := \mathrm{people}[v] + \mathrm{people}[u]$ $people [v] := people [v] + people [u]$ , where $\mathrm{people} = a$ $people = a$ at the beginning). Let $\mathrm{forward}[i]$ $forward [i]$ denote this sum for the directed topological sort at node $i$ $i$ and $\mathrm{backward}[i]$ $backward [i]$ denote the same for the reversed topological sort.

We now note that if there was no need to bidirectionalize an edge, the answer would be given by $\sum_{1 \le i \le N} a_i \times (\mathrm{backward}[i] - 1)$ $\sum_{1 \leq i \leq N} a_{i} \times (backward [i] - 1)$ .

The number of connection increases that result from the roadrollification of an edge $u \to v$ $u \to v$ is equal to $(\mathrm{forward}[v] - \mathrm{forward}[u]) \times (\mathrm{backward}[u] - \mathrm{backward}[v])$ $(forward [v] - forward [u]) \times (backward [u] - backward [v])$ . (This can be understood simply as [the number of people that can flow into $v$ $v$ that don't flow in from $u$ $u$ ] $\times$ $\times$ [the number of people that $u$ $u$ can reach excluding any that are already in $v$ $v$ and its subtree]).

Now the answer is given simply by $\left(\sum_{1 \le i \le N} a_i \times (\mathrm{backward}[i] - 1) \right) + \max_{1 \le j \le N-1} \left\{(\mathrm{forward}[v_j] - \mathrm{forward}[u_j]) \times (\mathrm{backward}[u_j] - \mathrm{backward}[v_j])\right\}$ $(\sum_{1 \leq i \leq N} a_{i} \times (backward [i] - 1)) + max_{1 \leq j \leq N - 1} {(forward [v_{j}] - forward [u_{j}]) \times (backward [u_{j}] - backward [v_{j}])}$ .

Time complexity: $\mathcal O(N)$ $O (N)$

Comments

There are no comments at the moment.