SbrTa's blog

HLD : SPOJ QTree . Need Help
By SbrTa, history, 8 years ago, In English

Getting WA in this problem. My Solution . I tried Heavy-Light-Decomposition for the first time. But don't know why getting WA. can you pls help me to find out the bug or any test case that my code fails..

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

»
8 years ago, # |
  Vote: I like it +4 Vote: I do not like it

You can refer to http://spojtoolkit.com/problems/ for finding test cases and their solutions to some of the spoj problems.

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

    May be there is a problem is the source code of QTree problem. i tried available test case 10.

    1
23
1 2 5
2 3 10
3 4 15
4 7 20
4 5 25
5  6 30
3 8 35
8 9 40
2 10 45
10 11 50
11 12 55
10 13 60
13 15 65
13 14 65
2 16 70
2 18 70
16 17 75
1 23 80
1 21 85
21 22 90
1 19 95
19 20 100
QUERY 12 6
UPDATE 7 145
QUERY 4 18
UPDATE 4 100
QUERY 5 20
UPDATE 18 250
QUERY 2 23
UPDATE 8 112
QUERY 6 16
UPDATE 9 155
QUERY 17 7
DONE

    this test case has 6 query. but the Generated output is only 55.

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

For this example:

1
23
1 2 5
2 3 10
3 4 15
4 7 20
4 5 25
5  6 30
3 8 35
8 9 40
2 10 45
10 11 50
11 12 55
10 13 60
13 15 65
13 14 65
2 16 70
2 18 70
16 17 75
1 23 80
1 21 85
21 22 90
1 19 95
19 20 100
QUERY 12 6
UPDATE 7 145
QUERY 4 18
UPDATE 4 100
QUERY 5 20
UPDATE 18 250
QUERY 2 23
UPDATE 8 112
QUERY 6 16
UPDATE 9 155
QUERY 17 7
DONE

Your code gives: 55

70

100

80

70

75

And my AC code gives:

55

70

100

250

70

100

A possible reason is here:

Your (incorrect):


 if(uchain==vchain){
            if(up>vp) swap(up,vp);
            r = max(r,Find(1,1,n,up,vp));
            return r;
        }

Correct:

 if(uchain==vchain){
            if(up>vp) swap(up,vp);
            r = max(r,Find(1,1,n,up + 1,vp));//think about of up + 1, (only when the query is on edges)
            return r;
        }

P.S sorry for my bad english.

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

    P.S2: I'm assuming it's the only mistake. I hope it helps you. P.S3: Draw the tree for thinking about the mistake.

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

      yes.. now i get it.. Here each node contains the cost of the edge between it's parent & itself. so "up" contains the cost of the edge connecting with it parent. But we need not count this cost actually. we need to count the immediate child of "up" in this chain through "vp". that's why it was WA.
      Thanks for reading my code & helping me to find out the bug..

      → Reply