CodeRed Bhindi Master And Graph

How to approach? /2short

Solutions here


Hope you understood the problem.

Quickly telling you have to find the shortest node to root (1) with value >x .
Now what can be done ?
Obviously we have to find nodes at a particular level with their values node 1 at level 0 (assume)
Nearest node meant by nearest level as all nodes in a level are at the same distance from the root .
SO at first our focus will be to store maximum value occuring in any particular level.
Then after that we will go inside the level.

HOW we will get nodes at a particular level??
Applying single source shortest path using bfs or dfs can help and we get nodes at a particular distance from the root.

Now we have to get all nodes at a level we can store them in a set of nodes at a particular level. After that we can apply queries inside the level set.

Now two tasks have to be performed update the maximum value of each level after queries of type 1 and extract the nearest level for each query this can be done with the help of segment trees . we will extract the minimum level whose value is greater than X you can learn how to do that with my code and . After getting the index of lowest level where our desired node lies we have to query inside the set of nodes stored at that level.

We have to find lowest value node in that level with value just greater than X that is its value must also be just greater than X . so what we can do is that we will store values in a pair in the set with two fields first field as the value of the node and second as the node itself now just find the lower bound of current level set with key value as {X,-1} AND TH NODE YOU GOT IN CURRENT LEVEL SET after applying lower_bound on that level set.


Now to handle update queries:

we have to first update the value of the node and than the level set to which the node belong to with new value Y AND FOR updating inside the set you can erase first the old node from the set and then insert the new node and for segment tree first find out which level the current node belongs to and then update the maximum value of that level accordingly with the new maximum value obtained from the set by its ending value levelset.end().

This way you can handle both the operations.

Solution link:

> Blockquote

This question would have been more interesting if C++14 or any stl would not have been allowed in the contest.


editorial of ** CodeRed Bhindi Master And Graph**