fsociety00's blog

SPOJ QTREE4
By fsociety00, history, 8 years ago, In English

Need help! I tried to solve SPOJ QTREE4. I used centroid decomposition, but still getting TLE (time limit exceeded). In my code, a query is processed in O(log(n)^2). How can I improve complexity? Any suggestions. Here is my code.

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

»
8 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
8 years ago, hide # |
← Rev. 2  
Vote: I like it +1 Vote: I do not like it

You may try a segment tree on the euler tour.You need to understand the euler tour/rmq algorithm for lca first (it can be found here https://en.wikipedia.org/wiki/Lowest_common_ancestor ).Then,build a segment tree holding the maximum value of lev[node1]-2*lev[node2]+lev[node3] where node1 and node3 are at first occurrence,both are white and node2 can be found between them(and is not neccesarily white)- lev[x] denotes the level of node x.Of course,you need to maintain some helping values (e.g maximum of lev[node1]-2*lev[node2]) but I find this a good segment tree exercise.Finally, you get O(logn) per update.

→ Reply
  • »
    »
    8 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    Can you please Elaborate on how to Maintain the Structure. A submission Code would be Extremely Helpful.

    → Reply
    • »
      »
      »
      8 years ago, hide # ^ |
      ← Rev. 2  
      Vote: I like it 0 Vote: I do not like it

      This function 'merges' 2 segment nodes(you now the answers for [a;b] in B,for[b+1;c] in C and you get them for [a,c] in A.I'm sorry it isn't very explicit, but i'll try to explain which is every part of the structure.The rest of the segment tree and building euler tour is more of a prequisite and I would PM if requested, but I find the most important part here.

      Code
      → Reply
  • »
    »
    2 hours ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    As far as I know, this doesn't actually work because in this problem, edge lengths are allowed to be negative, so the property that the LCA is the lowest-depth node in the range doesn't hold.

    → Reply