Editorial for COCI '11 Contest 3 #5 Plaće

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.

First, notice that we can represent the company hierarchy using a tree. Each node in a tree represents an employee, and corresponding subtree his subordinates.

If we traverse this tree using preorder, we will get a list of all the nodes. For every subtree, there is an interval in this list that contains exactly the nodes of that subtree.

L = {}
TRAVERSE(u):
    append u to sequence L
    for each unvisited v adjacent to u, do TRAVERSE(v)

We obtain the whole list by calling TRAVERSE(1).

We now need a structure that can increase some interval in $L$ ~L~ by a given value, and return the value of an element at a given moment. This can be done by using interval (tournament) tree, or Fenwick tree. Overall complexity is $\mathcal O((N+M) \log N)$ ~\mathcal O((N+M) \log N)~.

Comments

There are no comments at the moment.