Editorial for Yet Another Contest 7 P4 - Paparazzi

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

Clearly, we can model the towns as a tree.

Subtask 1

It suffices to naively simulate each operation, keeping track of every single paparazzo at all times. We can perform a BFS/DFS from a_i to determine where each paparazzo moves.

Time complexity: \mathcal{O}(NM)

Subtask 2

At any point in time, the nodes occupied by the paparazzi form a subtree (a contiguous subgraph of the tree). We need to maintain which towns have at least one paparazzo. There are only three cases:

  • a_i is part of the subtree, but not one of its leaves. The effect is that all of the leaves are pruned. We can handle this by maintaining the degrees of each node in the subtree, and maintaining a set of leaves.
  • a_i is a leaf of the subtree. The effect is that all the leaves are pruned, except for a_i.
  • a_i is outside the subtree. Let X be the node in the subtree which is closest to a_i. Let Y be the unique neighbour of X which is closer to a_i than X. The effect is that node Y is added to the subtree, and then all leaves other than Y are pruned. In order to find X and Y, pick any node in the subtree and consider the path from that node to the target node. One side of the path will be in the subtree, and the other side of the path will be outside of the subtree. X and Y are the nodes where these two sides meet, so we can compute X and Y using LCA and binary lifting.

Note that after each operation, at most one node is added to the subtree. Thus, the total number of times that a leaf is pruned across all operations cannot exceed N + M.

Time complexity: \mathcal{O}((N+M)\log{N})


There are no comments at the moment.