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

algorithm
Posted by ilucian1 15 Nov 2005 20:08
First of all I suppose the graph is a tree (M=N-1 and all vertices are connected, see the text). Is it a tree? I choose one vertex (let it be 1) and consider it as root. I perform breadth first algorithm starting from the root and obtain vertices in increasing order of distances (in the same time I obtain the parent for each vertex). The result is the array C[1..N]. From N downto 1 I search for available C[i] and P[C[i]] (P[C[i]] is the parent for C[i]). I mark C[i] and P[C[i]] not to be used furthermore (unavailable). The edge [C[i],P[C[i]] is part of solution

and the final result is WA on test 7...
what's wrong ?

Edited by author 15.11.2005 20:32
Re: algorithm
Posted by Lucian Ilea 25 Aug 2010 17:18
The algorithm was correct but I ignored the output format  ... AC now
Re: algorithm
Posted by ErikJ 3 May 2013 18:00
Hi,

I have the same problem with WA #7, in what way was the output format wrong?