Показать все ветки Спрятать все ветки Показать все сообщения Спрятать все сообщения |
Some test | Kollekcioner[Vologda, VML1] | 1416. Для служебного пользования… | 25 апр 2020 06:26 | 8 |
Some test Kollekcioner[Vologda, VML1] 15 авг 2007 00:23 If you have WA25 and low try this test: 8 9 1 2 1 2 3 5 3 4 3 4 5 4 3 6 1 3 7 2 3 8 9 6 8 9 7 8 8 AC answer: Cost: 24 Cost: 25 What? The right answer should be Cost: 24 Cost: -1 Reply to the upper Edited by author 04.04.2011 20:38 I think answer should be 24 24, as my program does. We can replace 3->8 with 3->6 and it changes nothing. In fact,it changes; What my program shows is 24 25 |
O(N^2) solution... | Dima_Philippov | 1416. Для служебного пользования… | 20 июл 2018 21:41 | 2 |
What is the O(N^2) solution of this problem? I wrote simply Kraskal & DFS with assimptoty O(E * Log(E) + V * E) and got Accepted in 1.156... I want to know O(N^2) solution of this problem... My 0.093 N square solution: 1) Compute MST with Kruskal in E logE. 2) For each pair of vertices in MST compute dp[u][v] the cost of largest edge on path from u to v. This can be done by calling N depth first searches. DFS runs in O(E) and there is N - 1 edge in a MST. So this step takes (N^2) time. 3) For each edge (u, v) that isn't in a MST try to relax answer with { MST_COST - dp[u][v] + weight(u, v) }. This step is done in O(E). So, the running time of this solution is O(ElogE + E + N^2) = O(N^2). |
WA #11 Help me! | letranloc | 1416. Для служебного пользования… | 13 июл 2018 21:52 | 3 |
I got WA at #11. I had tested all tests on discussion and It's print right answer! Can anyone tell me some tricks? i don't know the mistake!!! What's #11??? The same to me :( Can the author of the problem show the test case or someone give more tests, please? Edited by author 13.07.2018 21:54 |
WA on test 11 | So Sui Ming | 1416. Для служебного пользования… | 18 дек 2017 11:00 | 1 |
My codes passed all testcases mentioned in the forum using stable sort or sort in c++ but still got WA on test 11. Any idea? Edited by author 18.12.2017 11:01 Edited by author 18.12.2017 11:01 |
test 11st | jaxi | 1416. Для служебного пользования… | 6 авг 2015 18:38 | 5 |
i've got a wa on test 11st,could someone give me the test data? Edited by author 26.02.2011 11:03 Edited by author 26.02.2011 11:03 I've got a wa ,too. I need test data to find question. I got wa at 10th test. Who can tell me the data? Thank you ! sunzuhan@163.com 4 6 1 2 1 1 3 5 3 4 1 4 2 3 4 1 8 2 3 0 Have a try! The right answer is 2 4 At first I forgot something and failed at #11 However, my programme shows the answer 2 4, but i failed at #11. Who can tell me why? |
Prim got AC,Kruskal TLE #6 | twocoldz | 1416. Для служебного пользования… | 13 ноя 2013 23:01 | 1 |
RT. I want to know what data is on test #6 |
Test #11 Data | 1212187 | 1416. Для служебного пользования… | 4 ноя 2013 16:10 | 3 |
Can someone give me data of test #11? I have test all data in discussion section and got right answer but my program just stuck in test #11.... 4 6 1 2 1 1 3 5 3 4 1 4 2 3 4 1 8 2 3 0 is this test #11? |
Statement bug? | RybKMU | 1416. Для служебного пользования… | 5 дек 2012 10:23 | 1 |
"highly protable"? May be "highly profitable"? And "in those aairs"? May be "in those affairs"? Edited by author 05.12.2012 10:26 |
wa38 | lkjslkjdlk | 1416. Для служебного пользования… | 11 авг 2012 18:25 | 1 |
wa38 lkjslkjdlk 11 авг 2012 18:25 use sort, wa. use stable_sort, ac |
Useful hints about ranges of M (amount of edges) | Smilodon_am [Obninsk INPE] | 1416. Для служебного пользования… | 11 мар 2012 15:36 | 1 |
Note that M (amount of edges) could be as more as N^2. Tests #12 and #15 contain perhaps M equal about 250000. Edited by author 11.03.2012 16:06 |
I get WA11 before . Now I AC . Here is some hint | Eazy jobb | 1416. Для служебного пользования… | 8 дек 2011 11:48 | 1 |
Helpful test data: 6 6 1 2 8 2 3 3 3 5 2 2 4 7 4 6 2 2 5 6 Ans: Cost: 22 Cost: 25 Edited by moderator 12.11.2023 21:26 |
Is O(N^2) the fastest solution ? | N.M.Hieu ( DHSP ) | 1416. Для служебного пользования… | 25 окт 2011 16:23 | 6 |
I think O(N^2) ( Prim + DFS )is the fastest way to solve this problem , is it right ? Tell me, Why Kruscal+DFS doesn't work? I have TLE#12. Should I write Prim? I think Kruskal + DFS is enough. Maybe you need to optimize your code. Nguyen Dinh Tu ( DHSP ), my fiend , has got AC with the complexity O(N^3)( 0.89s ) . He used Prim , too. OK, then tell me, please, how to find the second answer? I use DFS... May be I should delete the largest vertic and run Kruscal again? You may try adding each non-MST edge to the MST and delete the longest MST edge in the cycle. I don't know how, but my O(n^2) solution works 0.312 sec) |
Weak tests | Zayakin Andrey[PermSU] | 1416. Для служебного пользования… | 10 янв 2011 13:28 | 2 |
Weak tests Zayakin Andrey[PermSU] 7 авг 2010 21:59 My O(M*M*log(N)) solution passed. New tests were added. 40 authors lost AC. |
wa #11 | Baurzhan | 1416. Для служебного пользования… | 8 авг 2010 09:10 | 5 |
wa #11 Baurzhan 12 июн 2010 21:19 My programm passes all tests from the forum and sample tests. Please, give me some tricky tests. One more question: is there test with N=1? (it's impossible according to the statement but somebody adviced to check this case. Is it nesessary?) Edited by author 12.06.2010 21:20 1. check your sorting algo (I used bucket sort at last) 2. don't stop at the first MST-free edge, try some more edges This helped me. |
TLE#12. Algo Kruscal doesn't work! Help :( | Alexey | 1416. Для служебного пользования… | 31 июл 2010 19:29 | 2 |
Please, tell me what kind of mistake can I have? I see that there are a lot of persons who has problems with Test#12. Is there smth speciale? Thanks. Edited by author 14.05.2006 15:27 I also have TLE 12 and write Kruskal and his advanced version with DSU. It doesn't meter. But when at finding secondcost i stoped finding, if secondcost became equal to firstcost i got AC at Java with 0.2 sec with complexity o(n^3) at worst case :-) Edited by author 31.07.2010 19:32 |
Is something wrong with sample #1? Need answer ASAP. | tedomir | 1416. Для служебного пользования… | 27 май 2010 00:10 | 2 |
4 6 1 2 2 2 3 2 3 4 2 4 1 2 1 3 1 2 4 1 Cost: 4 Cost: 4 1: why not 1>4(cost 2, minimum. Description says if transition between A > B is possible then B > A is possible too) That gives answer: 2 2:1>3(cost 1) then 3>4(cost 2), 1+2=3 That gives answer: 3 Anyone mind explaining why its 4 and 4 in sample? "choose the minimal possible set of trans-planet passages so that he could pass from any planet to any other one via those passages" If you choose 1-3 and 3-4, you can't reach planet 2 from the other planets. |
I've got WA on test 11. What's wrong? | Khlyzov Andrew | 1416. Для служебного пользования… | 21 апр 2009 21:42 | 11 |
Do we have to find two smallest mst that differ from each other by one edge? i got WA as well.can anyone tell me?i don't know the mistake The same :(( Please help me :( i have WA on test 12:) it's not the same:)) Maybe there is something wrong on your UFS(Union Find Set)... bug has been founded, thanks for replying :) may be this test will hel you 4 4 1 2 2 2 3 1 2 4 3 3 4 1 answer Cost: 4 Cost: 6 but my WA11 program return Cost: 4 Cost: 5 and this test 5 6 1 2 2 1 5 1 2 3 1 2 4 1 1 3 4 4 5 3 answer Cost: 5 Cost: 6 Edited by author 21.04.2009 22:22 |
How to solve this problem in 0.045s? | DK [Samara SAU 1: X2008] | 1416. Для служебного пользования… | 4 июн 2008 02:42 | 1 |
I've solved it only in 0.14s :( |
WA#12 Hint | AlexF [USTU Frogs] | 1416. Для служебного пользования… | 26 авг 2007 19:19 | 1 |
I had WA#12 when I've forgotten that the wights can be 0)) |
At last AC...Who got WA#12 can test this data: | Yitao | 1416. Для служебного пользования… | 30 июн 2007 18:39 | 2 |
6 6 1 2 8 2 3 3 3 5 2 2 4 7 4 6 2 2 5 6 The correct answer is: Cost: 22 Cost: 25 But the program made by me which WA 12 prints: Cost: 22 Cost: 20 I also got WA 12, but pass this test correctly... Ops, I forget that weight of an edge can be equal to 0. Edited by author 30.06.2007 20:00 |