Lakh's blog

By Lakh, history, 6 years ago, In English

I am trying to solve https://www.hackerrank.com/contests/world-codesprint-13/challenges/landslide.

Here given a tree of N(N<=2*10^5) nodes and Q (Q<=2*10^5) queries of 3 types:

1. d x y -- Remove the edge between city x and y if it exists else ignore this query.
2. c x y -- Add the edge between city x and y if previously an edge was present between x and y else ignore this query.
3. q x y -- Find the distance between x and y if there exists a path between x and y else print "impossible".
My approach:

I first performed dfs to store the in[] and out[] time of each node and code for finding LCA of two nodes. Now I created a segment tree on the basis of the in[] array and initialized each node to value 1 meaning that all nodes are initially form a single connected component. I took a variable counter=2. 

Now for query of first type , suppose x is parent of y then I just updated all nodes in subtree of y to value counter using lazy propagation such that it represents a different component and increment counter by 1.

For query of 2nd type, if x was parent of y previously, then I just updated the entire subtree of y to the current value in node x so that entire subtree of y is again attached to subtree of x and y becomes part of the component to which x belongs.

For query of 3rd type I first computed LCA of x and y then determined the current values of node x, node y and node[LCA(x,y)]. If all the three values are not same then this means that x and y are not connected else i just print the distance between the nodes x and y as dis[x]+dis[y]-2*dis[LCA(x,y)]

Some of the tescases are failing. I am not able to understand what is wrong with my approach. Please suggest the problem with this approach.

My code: https://ideone.com/cXf4NX

  • Vote: I like it
  • +5
  • Vote: I do not like it

| Write comment?