My method for this problem is way different, I did a complete simulation of where each person is each second. Still got ac for 100 points by using some smart optimization.
- Convert to a weighted tree. and remove all intermediate nodes with only 1 child(Assasins never get killed here). For example, if we have a tree with 4 nodes connected like this 1-2-3-4,
i.e., 2’s only child is 3 and 3’s only child is 4.
I will connect 1-4 and store weight[1,4] =3.
- Store a parent array for each node in the new graph.
- Now do the simulation like this, among all assassins, find the minimum distance to their parent,
send all the min ones to their parent, rest all reduce the distance to their parent by the min value. Increase time by that value.
- Now, make a temporary variable to keep traversing up the tree to check if an assassin is present there. if present, move to the topmost node where the assassin is present in that path and make parent of all the nodes in this path as the topmost node where the assassin is present.
Keep doing this till some people reach 1.
Alternative for 4, do DFS from the assassins that reached their parent node on its subtree and find who all will reach there.
Got AC with no DSU or DFS for the simulation of the entire system.(did dfs to convert to weighted tree and getting parent array only)
With some bit of extra code My code can even tell the position of a given assasin at a given instant for 10^6 queries ,lol