Editorial for An Animal Contest 2 P6 - Koala Transport System - Olympiads Online Judge

Editorial for An Animal Contest 2 P6 - Koala Transport System

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.

Authors: Riolku, ThingExplainer

Subtask 1

First, we run a DFS from node $1$ $1$ to build a $retrace$ $r e t r a c e$ array. Let $retrace[i]$ $r e t r a c e [i]$ be the next node on the path from $i$ $i$ to $1$ $1$ , and $retrace[1]$ $r e t r a c e [1]$ will store a dummy node, such as $0$ $0$ .

Let $dist[i][j]$ $d i s t [i] [j]$ store the minimal distance from any node on the path $1 \dots i$ $1 \dots i$ to node $j$ $j$ . We can fill the $retrace$ $r e t r a c e$ array by running a multi-node BFS for every node $i$ $i$ . To do this, simply use the $retrace$ $r e t r a c e$ array and push the nodes from the path $i \dots 1$ $i \dots 1$ into the queue, and perform BFS normally.

Now, we can process the queries by setting each node as $v$ $v$ and summing the distance for all $x_i$ $x_{i}$ by using the $dist$ $d i s t$ array, and taking the minimum value after setting all $N$ $N$ nodes.

Time Complexity: $\mathcal{O}(N^2 + QN)$ $O (N^{2} + Q N)$

Subtask 2

To solve this subtask, we only need to run $3$ $3$ DFS for the single query.

We initialize an array $subtree$ $s u b t r e e$ to store the number of feeding grounds in the subtree of node $i$ $i$ . We can fill up this array by running a DFS from node $1$ $1$ .

We now make the observation that the best teleportation path sets $v$ $v$ as a leaf node. Why? Let's say that the best teleportation path does not set $v$ $v$ as a leaf node. We can make this teleportation path better by setting one of the children of $v$ $v$ as $v$ $v$ , let's call this child $w$ $w$ . This allows any feeding grounds in the subtree of $w$ $w$ closer access to a teleporter and decreases or maintains the total distance travelled from all feeding grounds to node $1$ $1$ .

Let $totaldist$ $t o t a l d i s t$ represent the total distance travelled from all feeding grounds to node $1$ $1$ without the aid of any teleporters and $m$ $m$ represent some total distance travelled from all feeding grounds to node $1$ $1$ that can be achieved with the aid of teleporters. We note that $m$ $m$ is just $totaldist$ $t o t a l d i s t$ subtracted by some distance $d$ $d$ .

Therefore, we will attempt to maximize $d$ $d$ .

We now run a DFS with an additional $currsum$ $c u r r s u m$ variable which stores the current sum of the distance that can be subtracted if we have teleporters from $1 \dots u$ $1 \dots u$ , where $u$ $u$ is the current node we are running DFS on. For all nodes $v$ $v$ in the subtree of $u$ $u$ , we set the node $v$ $v$ as a teleporter by simply increasing $currsum$ $c u r r s u m$ by the number of feeding grounds in the subtree of $v$ $v$ . This is because all feeding grounds in the subtree of $v$ $v$ now have $1$ $1$ less distance to travel to reach a teleporter. When we reach a leaf node, we simply set $maxsubtract$ $m a x s u b t r a c t$ to $\max(currsum, maxsubtract)$ $max (c u r r s u m, m a x s u b t r a c t)$ .

We now run our last DFS which will get the total distance for all feeding grounds to node $1$ $1$ if there were no teleporters installed. To do this, keep a $dist$ $d i s t$ variable when running DFS to store the distance from the current node to node $1$ $1$ . Now, for all feeding grounds $x$ $x$ which we encounter during our DFS, we can simply add our $dist$ $d i s t$ variable to $totaldist$ $t o t a l d i s t$ .

Our answer is simply $totaldist - maxsubtract$ $t o t a l d i s t - m a x s u b t r a c t$ .

Note that the last $2$ $2$ DFS can be merged for a faster runtime.

Time Complexity: $\mathcal{O}(N)$ $O (N)$

Subtask 3

Let's consider a set of candidate locations $c$ $c$ .

Suppose we consider the root as our candidate. Our answer would be the sum of the depths of the feeding locations.

Now suppose we have a different candidate location. How much do we save by moving the node $v$ $v$ from the root to such a location? Every time we "move in the direction of a feeding location", we save $1$ $1$ unit of time per feeding location. A good way to calculate this is for each feeding location, add $1$ $1$ to every node on the path from it to the root. In order to determine the amount of time we save, we can simply query the path sum of our node $c_i$ $c_{i}$ .

The final observation is similar to one noted in the previous subtask: leaves are always optimal. However, we see that choosing a feeding location is always at least as optimal as a leaf, since anything lower than the lowest feeding location is not more optimal.

Hence, we consider only the feeding locations as candidates. To implement path update and path query efficiently, we can use HLD with two BITs, although other solutions exist.

Time Complexity: $\mathcal{O}(Q \log^2 N)$ $O (Q \log^{2} N)$

Comments

There are no comments at the moment.