Editorial for New Year's '17 P7 - Santa's Deliveries - Olympiads Online Judge

Editorial for New Year's '17 P7 - Santa's Deliveries

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.

Subtask 1

Simply try every possible path, and check each of the fireplaces below at every move.

Time Complexity: $\mathcal{O}(CN^2)$ ~\mathcal{O}(CN^2)~

Subtask 2

The same as subtask 1 but a bit bigger, there is no special trick for only fixing once.

Subtask 3

Take all the fireplaces and store them as a pair of <# of parents, index>. Sort by the number of parent fireplaces from greatest to least. This lists the possible paths from best to worst. During each update, check if the best path is still traversable. If it is, print it; otherwise move on to the next best path and check again. You can use algorithms such as HLD to reduce the time required to check each path.

Time Complexity: $\mathcal{O}((N+C) \log N)$ ~\mathcal{O}((N+C) \log N)~

This can also just be solved with a more optimized brute force.

Subtask 4

Realize that the entire tree is now laid out as a path, which can just be treated as an array containing each fireplace's distance to the chimney. During each update, simply take the lowest delay of all the grapple guns and binary search for the first fireplace where Santa would have to stop.

Time Complexity: $\mathcal{O}((N+C) \log N)$ ~\mathcal{O}((N+C) \log N)~

Full Solution

We can view the grapple guns placed at the fireplaces as blocking off certain routes for Santa. To determine what range of nodes each grapple gun blocks off, we must look at 2 things: its delay and the path to the chimney.

For simplicity, we will refer to the distance from a fireplace to the chimney as its "depth".

One case is that the depth is lower than its delay. This means Santa can get to the fireplace and continue his route before the grapple gun fires, so we ignore any grapple guns for which this is the case.

Otherwise, we search for the highest fireplaces whose depth is no less than the delay. If the depth is greater than the delay, Santa cannot reach the fireplace before it fires, and the route is effectively blocked off. The situation where the depth is equal to the delay is stated in the problem statement, and is again blocked off.

Once we find out the highest fireplace that is blocked off, we need to use a segment tree to range update the area blocked off. Before we can have a range update segment tree though, we need to index the nodes in the Euler tour order with a simple DFS. Now to find the answers, we have a multiset in each node of the segment tree that stores blocked off values. If a node's multiset has a value, then it is blocked off and its children are irrelevant. We take the lowest value in the multiset as the answer. If the multiset is empty, we take the answer of the node's children. After each update, the answer will be stored at the very top node.

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

Comments

1

thomas_li commented on Nov. 12, 2024, 12:49 a.m. ← edited →

I have a solution that works in $\mathcal{O}(C \log N)$ ~\mathcal{O}(C \log N)~. Consider making an array $bad[u]$ ~bad[u]~, where $bad[u] > 0$ ~bad[u] > 0~ if we can't reach $u$ ~u~, and $bad[u] = 0$ ~bad[u] = 0~ if we can reach $u$ ~u~. Suppose we start with all $bad[u] = 0$ ~bad[u] = 0~, considering each delay as initially infinity.

Now if we set a finite delay at $u$ ~u~, which nodes can we no longer reach? Clearly, all the nodes that have to travel through an ancestor of $u$ ~u~, where that ancestor's distance from $0$ ~0~ is at least our delay. It's easy to see that these nodes are exactly the subtree of the highest ancestor of $u$ ~u~ where its distance is at least our delay. If such an ancestor exists, we can increment the subtree's bad values in $\mathcal{O}(\log N)$ ~\mathcal{O}(\log N)~ with a lazy segment tree. To find that ancestor, we can use binary lifting.

To change a delay, we can simply subtract the previous contribution to $bad$ ~bad~, and add our new contribution.

Then we just need to find out the maximum depth of a node with $bad[u] = 0$ ~bad[u] = 0~. That can be found by maintaining the minimum bad value in the segment tree, along with the maximum depth of a node having the minimum bad value.