HLD : SPOJ QTree . Need Help

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

Автор 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..

hld, spoj qtree, heavy-light

SbrTa
8 лет назад
5

Комментарии (5)

Написать комментарий?

likecs

8 лет назад, # |

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

→ Ответить

SbrTa

8 лет назад, # ^ |

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.

→ Ответить

LuaXD

8 лет назад, # |

← Rev. 3 →

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

100

And my AC code gives:

100

250

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.

→ Ответить

LuaXD

8 лет назад, # ^ |

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.

→ Ответить

SbrTa

8 лет назад, # ^ |

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

→ Ответить