Editorial for LCC '22 Contest 2 S4 - Walnut Warfare - MCPT: Mackenzie Competitive Programming Team

Editorial for LCC '22 Contest 2 S4 - Walnut Warfare

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: BattleMage_

There are many equivalent ways to solve this problem, but one of the solutions is the following:

Run BFS starting from nodes with squirrels on them and for each node in the tree store $d[i]$ ~d[i]~, the minimum amount of time it takes any squirrel to get there.

Then, run DFS starting from the root node, keeping track of the current time limit $t$ ~t~, (the maximum amount of time that may be used to get to node $x$ ~x~ without any squirrels catching up). If $t < 0$ ~t < 0~, no nodes in the subtree of $x$ ~x~ can ever make it to the root. If $t \ge 0$ ~t \ge 0~, it is possible to make it from $x$ ~x~ to the root and each subtree rooted at $y$ ~y~ must be traversed with an updated $t$ ~t~ given by $t' = min(t - 1, d[y])$ ~t' = min(t - 1, d[y])~ .

There are some edge cases that must be specially handled. For example, if Sandy can make it to the root node in the same second that a squirrel would reach it, she can still get away because she moves first. Also, the root node should not be counted in the answer according to the problem statement.

Time Complexity: $O(N)$ ~O(N)~

Comments

There are no comments at the moment.