shashanka136's blog

By shashanka136, history, 4 weeks ago, In English,

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

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

»
4 weeks ago, # |
Rev. 2   Vote: I like it +38 Vote: I do not like it

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.

  • »
    »
    4 weeks ago, # ^ |
    Rev. 2   Vote: I like it +3 Vote: I do not like it

    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.

  • »
    »
    4 weeks ago, # ^ |
    Rev. 2   Vote: I like it -8 Vote: I do not like it

    Thank you very much, I used what you told and it worked.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Ignore my above comment understand the mistake now. Again thank you!!!

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by shashanka136 (previous revision, new revision, compare).