Блог пользователя shashankagrawal

Getting tle in using Common segtree in HLD, but not in Different segtree for each heavy path
Автор shashankagrawal, история, 4 года назад, По-английски

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 jef

  • Проголосовать: нравится
  • +2
  • Проголосовать: не нравится

»
4 года назад, # |
← 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.

→ Ответить
  • »
    »
    4 года назад, # ^ |
    ← 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.

    → Ответить
  • »
    »
    4 года назад, # ^ |
    ← Rev. 2   Проголосовать: нравится -8 Проголосовать: не нравится

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

    → Ответить
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    → Ответить
»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить