Show all threads Hide all threads Show all messages Hide all messages 
WA 30  Disintegrator  1389. Roadworks  18 Nov 2019 19:14  4 
WA 30 Disintegrator 8 Apr 2014 03:36 I have WA 30, what did you do to AC? Ok, I got AC after lots of WA 30 attempts by iterating over the input in the reversed order, which makes no sense to me. My current best guess is that test #30 is broken, so there are at least two correct answers and it accepts only one of them as correct. Of course, my algo can delete edges in different order depending on the order in which it iterates over them, but I'm pretty sure it always removes the maximum number of edges. 
TO WA30  ELEN  1389. Roadworks  6 Jul 2018 09:38  1 
You guys have to sort the roads to be the same sequence as the input means first input,first output 
WA5 test (AC program)  Gleb  1389. Roadworks  2 Jul 2018 14:15  1 
9 8 1 2 1 6 1 8 1 3 1 4 4 5 1 7 7 9 Answer: 3 7 9 1 2 4 5 
WA 11  So Sui Ming  1389. Roadworks  6 Sep 2017 15:00  1 
WA 11 So Sui Ming 6 Sep 2017 15:00 I used greedy search on sorted edges in increasing order of sum of degrees of vertices (of edge). Should I refine my compare function? Other hints? 
WA#2, HELP!!!!  ZiV  1389. Roadworks  9 Oct 2015 08:35  3 
Please help me, what is wrong with my solution.... Const MaxN = 100000; Var b : array[1..MaxN] of boolean; c : array[1..2,1..MaxN] of longint; c_num,n,m,i,x,y : longint; BEGIN Readln(n,m); Fillchar(b,sizeof(b),true); Fillchar(c,sizeof(c),0); c_num := 0; For i := 1 to m do begin Read(x,y); if b[x] and b[y] then Begin Inc(c_num); c[1][c_num] := x; c[2][c_num] := y; b[x] := false; b[y] := false; End; End; Writeln(c_num); For i := 1 to C_num do Begin Writeln(c[1][i],' ',c[2][i]); End; END. Try such test... :) 4 3 2 3 1 2 3 4 Correct answer is 2 1 2 3 4 I don't think, that greedy is a good idea... Try this one 4 3 1 2 1 3 3 4 Correct Answer: 2 1 2 3 4 
Идея  Felix_Mate  1389. Roadworks  5 Jul 2015 12:29  1 
Идея Felix_Mate 5 Jul 2015 12:29 Я получил АС! Сложность O(N+M)=O(2N). Стандартный обход в глубину, но несколько изменённый. Важно чтото заметить про висячие вершинки. Edited by author 07.07.2015 00:02 Edited by author 07.07.2015 00:02 Edited by author 07.07.2015 00:02 
Can you give me some TEST i have WA 30. Thank you  Tukenov  1389. Roadworks  3 Jul 2015 14:36  2 
Can you give me some TEST i have WA 30. Thank you I have WA 30 too((( What did you do to AC? 
Problem 1389 "Roadworks" was rejudged  Vladimir Yakovlev (USU)  1389. Roadworks  4 Apr 2014 11:33  4 
New tests were added. All solutions were rejuded. 260 authors have lost AC. The most common verdict was Runtime error (stack overflow). I just add to my code #pragma comment(linker, "/STACK:66777216") and get AC =) I sent more tests for TLE. Your tests were added. AC solutions were rejudged. 30 authors lost AC 
explain recent rejudge?  Vyacheslav Kim  1389. Roadworks  21 Mar 2014 02:40  2 
Hi, I had an accepted solution 3 years ago and now I have no idea what was wrong/right. Looking at my previous solution that now gets TLE, it was Kuhn matching algorithm. Did the constraints change or did you just add better tests? OK, I have no idea how could I possibly come up with such solution and how come it passed the tests before :P 
Some test cases [AC]  Lucas Negri  1389. Roadworks  11 Aug 2013 18:09  3 
Nevermind. Solved. I've detected my error with this input: 11 10 1 2 1 3 2 4 2 5 3 6 3 7 4 8 5 9 6 10 7 11 5 roads can be blocked. Edited by author 29.08.2011 22:33 The answer is: 5 1 2 4 8 5 9 3 6 7 11 
Can i use Greedy ?  Lifanov  1389. Roadworks  24 Jul 2013 17:15  5 
I take the list (any City with 1 road) and delete this road, then going to connected city and mark all road from it as nondelete, then i going to near city and repeat first step. For example 5 4 1 2 2 3 3 4 3 5 Start with 1 City, delete (1 2) then go in 3 city, and remove (3 4) or (3 5)? Why WA2 ? Sorry fo my English. here is example: 8 7 1 2 2 3 3 4 3 5 4 7 7 8 5 6 Answer depends on the way you go from city 3. Yes. But your algorithm probably realy work wrong. My greedy: While graph is not empty 1. We choose any vertex v: deg(v)=1 (e=(v,u)) 2. Add to the answer edge e. 3. Delete v and u with all its edges from the graph. @Burunduk1 I used the same greedy algorithm as u did but I get WA#2, can u please help me? Edited by author 24.07.2013 17:16 
algorithm  ilucian1  1389. Roadworks  3 May 2013 18:00  3 
First of all I suppose the graph is a tree (M=N1 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 The algorithm was correct but I ignored the output format ... AC now Hi, I have the same problem with WA #7, in what way was the output format wrong? 
To admins: Test data is really, really, really weak  Douglas Cardoso  1389. Roadworks  23 Jun 2012 13:47  2 
Please check my submission 4323013. It gets AC although to the input 4 3 1 2 2 4 4 3 it answers 1 2 4 when the right answer is clearly 2 1 2 3 4 Your test was added, 15 authors lost AC. 
How to be fast?  Artem Khizha [DNU]  1389. Roadworks  13 Dec 2011 15:35  2 
Greetings! I have just solved this problem with DP on a tree via DFS, but it appeared to be much too slow (0.25s), though I expected a better result. There's a tree in this problem, so totally solution must be O(N). May any precial tricks be there or I just did something wrong? You need only 2 DFS. This solution get AC in 0.08s. 
The next K lines should describe these roads in the same form as they were given in the input.  Edric Mao  1389. Roadworks  12 Nov 2011 15:00  1 

biparite matching  Baurzhan  1389. Roadworks  6 Jul 2011 18:11  7 
is it possible to find biparite matching for n or n logn? if we divide graph into 2 parts  maximal matching is the answer. But biparite matching founding time is NM(maxflow) so N*N(because it's tree). I got AC using bipartite matching :) I'm too  HopcroftCarp rulezz=) i use dynamic progrmaming and got AC in O(N), i think the best the algo too find maximum biprate matching ue O(nm), what's your algo????? sorry for y poor english. AFAIK, Fastest biparite matching algorithm  Hopcroft Carp, with complexity E*sqrt(V); Vnum of vertices; E  num of edges; Given graph is a tree, so it's possible to color it into 2 colors, after that, take all black vertices as one part, white as other part and find max matching between them. I can't give strict evidence of this approach but it intuitively understandable  just draw sample output on the paper and everything will become clear=) You can see my code > i shared my account here http://acm.timus.ru/forum/thread.aspx?id=25749&upd=634266195834002500 Just look my submission. this algo is very similar to Dinica algorithm, are they identical? ну, не знаю даже! Кун прошел за 0.9 
Can you give me test #14? my program is crash  dmitri_quick  1389. Roadworks  6 Dec 2010 22:08  2 

TO ADMINS: weak testdata  Oracle[Lviv NU]  1389. Roadworks  13 Nov 2009 18:17  1 
Please, add test, where N=100 000, and graph is a line. It will cause stack overflow (at least for my solution). 
WA#5! Please help!!!  Crash_access_violation  1389. Roadworks  10 Aug 2009 13:16  1 
I use greedy algo, but I got WA :( Please give some useful tests. 
what means the subject ?  lian lian  1389. Roadworks  15 Feb 2009 18:00  1 
the answer needs to cover the all vertex ? Edited by author 15.02.2009 18:10 