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

HLD : SPOJ QTree . Need Help
Автор SbrTa, история, 8 лет назад, По-английски

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..

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

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

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

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

    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.

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

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.

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

    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.

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

      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..

      → Ответить