|
|
InPut 5 5 1 4 4 5 5 1 1 2 2 3 OutPut 3 2 1 4 5 1 subj This might help: input: 4 4 1 2 1 4 2 3 4 3 output: 1 1 4 3 2 1 I wrote a program about this problem but wa4.... I found an AC code but it can not pass this data,and I can pass. 8 12 1 2 2 3 3 4 4 1 1 5 2 6 3 7 4 8 5 6 6 7 7 8 8 5 here is my answer: 4 5 6 7 8 5 1 2 3 4 1 6 2 7 3 8 4 here is ac code answer: 7 1 2 3 1 4 3 4 5 1 6 5 6 7 1 8 7 8 9 1 10 9 10 11 1 12 11 12 13 1 14 13 14 2 I think he is wrong. Please add this kind of data. And I wanted to know the test for test 4. Could you please tell me? At last,sorry for my poor English. I got an AC,if you wa4,you can try this test 20 25 5 14 11 17 19 7 1 12 3 1 10 8 2 6 17 4 11 10 2 4 6 9 3 16 7 11 20 4 6 10 9 12 16 9 9 15 17 5 11 13 15 6 13 9 17 9 19 8 18 17 the right answer is three , why the answer which you tell me is five ? you played a trick on ME !! 3 10 6 15 9 17 14 5 17 18 20 4 2 6 9 16 3 1 12 9 13 11 7 19 8 10 11 17 4 if your algo use euleraen tour and also add edge to the graph, note that the edge can be over that 20000. this test is good: 20000 19999 1 2 1 3 1 4 . . . 1 20000 GOOD LUCK & HAPPY NEW YEAR!!! I wrote a program about this problem and passed it today. But in fact,my program can't pass this data: 4 4 1 2 2 1 3 4 4 3
Here is my answer: 1 3 4 3 0 0 0 It is not correct obviously. Please add this kind of data. At last,sorry for my poor English. It seems that there is only one connected-graph. ...And no repetitive edges. Edited by author 01.03.2009 12:27 How do this faster? 1) Adding virtual edges to pairs of vertices with odd degree 2) Building Eler circuit in new graph. 3) Cutting circuit by virtual edges. But Graph is undirected and when we removing edges in classic stac algorithm we should use set-class as dynamic Adj list for each vertex instead of vector-class How to do it even faster: add virtual edges between new virtual point and odd-degree nodes. Just O(N) overhead. (AC in 0.046 sec) Edited by author 13.08.2008 05:28 As for bidirectionality - just add edges twice and maintain bidirectional indexation between them. Or add all edges to base-0 arraay in the order (v1;v2), (v2;v1), (v3;v4), (v4;v3), etc... then "x XOR 1" will be index of backwards edge. Please give me this test. I cannot find a mistake in my program ((( Does anybody know, how to cope with it? (Idea of my solution: Euler Cycle). System stack is not so bad, there must be error in algo. Euler cycle can be found in O(E), though depth of DFS can be O(V). i got wa 5 I also have Crash! Somebody! Help me! I cant understand what`s wrong! Maybe my Euler procedure have som bugs... Edited by author 17.01.2007 13:44 no problem)))) ~~~delete this message~~~ I had Crash because of the size of stack My program is wrong! But I got AC! I took part in the live contest yesterday and it is unfair to participate in this contest too. But I have submitted 2 problems only (F and C), which were not solved during that contest. I am sorry. P.S. Problem C is brilliant. My respect to the author. And I have solved it using less than 1 Mb ;) P.P.S. I wonder if Mr. Kopeliovich took part in CBOSS yesterday... I took part in CBOSS yeasterday. Only 7 problems :((( I am sorry too... :( But I could not imagine that only 8 ACs will give second place today! I only trained to write fast and to get AC from first try. PS: "less than 1MB" ...but using more than 1 sec of time :) PPS: Why wonder?? > I only trained to write fast and to get AC from first try. Me too. > PS: "less than 1MB" ...but using more than 1 sec of time :) If I rewrite my code into C++, it will work about 0,6 sec in fact. But I can speed up my solution on Pascal too (while deleting the edge I look though all of them within linear time, but logarithmic time seems to be possible). > PPS: Why wonder?? "Wonder" means "want to know" ;) |
|
|