shashanka136's blog

By shashanka136, history, 3 weeks ago, ,

Can any one help me with why this solution is getting TLE, are the constants too high? My solution is here in which I made single segment tree for whole of the tree And the one which got AC, in which I made different segtree for each heavy path, is here

Edit :- Got it now, Thanks to bessiethecow

• +2

 » 3 weeks ago, # | ← Rev. 2 →   +38 Your HLD looks wrong. You have if(adj[v][0] != p && tot[u] > tot[adj[v][0]]) { swap(u, adj[v][0]); } and later up[u] = (u == adj[v][0] ? up[v] : u); So if the adj[v][0] = p for every node, the complexity blows up. Adding the following code fixes it: if(adj[v].size() >= 2u && adj[v][0] == p) { swap(adj[v][0], adj[v][1]); } You implemented it slightly differently in the other submission, so it doesn't have the same problem, but it still looks a bit wrong. The tot variable in dfs_tot looks like is supposed to be the size of the subtree, but then you do tot = cr; which makes no sense.
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   +3 But I have also done ~~~~~ if(u == p) continue; ~~~~~So, If any node has atleast 1 child and adj[v][0] = p, then it will surely be swapped with adj[v][1], and then loop continues, and hence adj[v][0] will never be p except for leaves. So, Can you please elaborate more?And Sorry for the confusion, But in the second submission I used a different idea for forming the heavy paths, which is I am using length of heavy path down the node instead of subtree size of that node.
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   -8 Thank you very much, I used what you told and it worked.
•  » » 3 weeks ago, # ^ |   0 Ignore my above comment understand the mistake now. Again thank you!!!
 » 3 weeks ago, # |   0 Auto comment: topic has been updated by shashanka136 (previous revision, new revision, compare).