ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1069. Prufer Code

Whats wrong with my algo?
Posted by teamSaratov 28 Jul 2006 00:43
Can anyone please help me to find what's wrong with my algo? I've got WA on test #5

1) Reading.
.....a) read i - num of vertex
.....b) increase the i'th power (power - number of vertexs which arre linked with the i-th)
2) Increase the powers of all vertexes except the Nth (the last one).
3) Recovering of thrown queue.
.....for 1 <= i <= N-1 do
.....//it is clear that we had thrown away N-1 vertexes
..........a) Find K - the vertex with minimal power (power=1). We have tree => we can always find such vertex. I'm using the search with barrier.
..........b) Let Power(K)=0 (it means we had thrown it away).
..........c) Decrease the power of i-th given (!) vertex, because it was linked with the Kth.
4) Writing Out.
.....a) for 1 <= i <= N-1 do
..........i) Recover Q - the queue of vertexes, linked with the i-th.
..........ii) QSort(Q);
..........iii) Write sorted Q.
.....b) for i=N do
..........Find in given array of vertexes the entering(-s) of N and write the corresponding vertex in thrown away queue.

I hope it's hardly diffucult to understand what i wrote ;)
Anyway, I can explain it smth if not clear
Re: Whats wrong with my algo?
Posted by teamSaratov 28 Jul 2006 22:33
I've found my mistake (it was in step 4).
So, now I have AC wish everybody the same
;)