Показать все ветки Спрятать все ветки Показать все сообщения Спрятать все сообщения |
TLE is a problem | goodcoffee | 1198. Коррупция | 26 апр 2023 04:50 | 1 |
but Kosaraju + scanf + MS compiler may help here |
If you have TL 50 or ML 50 | andreyDagger | 1198. Коррупция | 25 янв 2022 16:54 | 1 |
Instead of writing this: vector<int> g[2001]; write this: vector<vector<int>> g;............g.resize(n + 1); Edited by author 09.06.2022 23:22 |
If you have TL | gaporf | 1198. Коррупция | 7 авг 2021 06:15 | 3 |
If you have TL on test 21, 49 or 50 you should use gets. I get AC with 0.3 s. I was getting TL21, but once I've added "ios_base::sync_with_stdio(false)", I got AC |
unable to go below 1sec and 10MB | Tbilsu_Irakli Khomeriki | 1198. Коррупция | 16 сен 2018 17:31 | 1 |
can anyone please share solution that works under 1 sec and under 10MB, I would really appreaciate it. my email is: ikhomeriki@gmail.com |
Use 'Visual C++ 2013' instead of 'G++ 4.9 C++11' | [SESC]Fstilus ♂♊🎧皇 | 1198. Коррупция | 7 дек 2016 21:29 | 1 |
Same solution: Visual C++ 2013: Accepted 0.686 8 120 КБ G++ 4.9 C++11: Time limit exceeded 21 1.513 3 924 КБ oh my code.. |
WA 31 (help) | Combatcook | 1198. Коррупция | 28 июл 2016 14:51 | 1 |
Hello! If you have WA 31 (I haven't seen these yet, but all is possible:D), try these test: 5 2 0 3 0 1 0 3 5 0 4 0 -- 4 5 0 Maybe it will help you. Edited by author 28.07.2016 14:58 |
Time limit is corrected | Vladimir Yakovlev (USU) | 1198. Коррупция | 4 фев 2016 08:24 | 1 |
The new time limit is 1.5 seconds. About 50 more authors have AC now, while a few have lost their AC |
just dfs giving TLE in test case 21 | Raj Manvar | 1198. Коррупция | 25 дек 2015 15:10 | 1 |
my program just does dfs three times on the graph.... and so has order O(|n| + |e|) where n is number of nodes and e is edges till gives TLE in case 21... :( do we need a better algorithm than this as well...? |
Weird tl | -XraY- | 1198. Коррупция | 13 ноя 2015 23:55 | 1 |
Are you sure you want tests with a lot of input data, such that scanf("%d",...) doesn't work on time? I don't think this is okay. There is a read problem with new g++ compilators. |
use scanf instead of cin | wangbicheng1 | 1198. Коррупция | 7 ноя 2015 10:53 | 1 |
I got accepted in 0.78s using scanf instead of cin which makes me TLE |
O(N^2). Is there better solution? | Oracle[Lviv NU] | 1198. Коррупция | 10 авг 2015 12:58 | 6 |
I divided given graph into biconnected components, and then worked with created DAG. This solution is O(N^2) and runs in 0.203 seconds. But there are solutions with better time. Is there faster algo for this problem? P.S. sorry for bad english(( The input in this problem requires O(N^2) time, so the better complexity cannot be achieved :) Your solution O(N^2*log(N)) in worst case, because the input in this problem requires O(N^2*log(N)) time, so the better complexity than it cannot be achieved. How to divide graph into connected components in O(N^2)? You can use Tarjan's algorithm to find strongly connected components |
Best complexity | Alexandru Valeanu | 1198. Коррупция | 5 янв 2014 13:44 | 1 |
The complexity of the optimal algorithm is O(N + M), because the input is not O(N ^ 2) is O(M). |
stuck on 49 TLE ( and only one who get wa on 46 :) ) | qulinxao | 1198. Коррупция | 13 авг 2012 20:49 | 2 |
is graph just full on 49 test? probably nop , cose i test prog on full 2000 less then .1sec |
I'm using Warshall's algorithm, but TLE 21 | Andrew Sboev | 1198. Коррупция | 25 июл 2012 00:20 | 3 |
Why? What is a key point of this task? You can try to condense your graph first. It helped me to avoid TLE21 with my O(N^3) DFS and indeed would help your Floyd-Warshall. However, I am not sure whether there is not a better solution — my time is 0.25s that is so far from the best 0.046s. Thx, I will try this way. |
WA 12 | THE_SCORPION | 1198. Коррупция | 27 апр 2012 14:08 | 6 |
WA 12 THE_SCORPION 4 май 2006 23:54 Please help me!!! I can't pass 12 test. I tried all possible test's: with one senators, with not coherent senators, with all coherents senators and many-many others...In my computer always work, but not on this site. Maybe someone can say me what is the 12 test? Try this test, may it'll help you 7 2 7 0 3 0 4 0 5 0 3 0 1 0 6 0 try this test: 9 3 5 0 3 0 2 8 0 5 0 4 6 0 7 9 0 6 0 9 0 0
Re: WA 12 olpetOdessaONU [1 2/3] 12 июл 2011 22:29 My program passed all these tests but still have WA12 :( Re: WA 12 Tbilisi SU: Dolidze Alexander 27 апр 2012 14:08 |
fast solution | Denis Tapyshpan | 1198. Коррупция | 2 дек 2011 01:13 | 1 |
My solution works for 1.2 sec(I used Warshall's algorithm). One can find out that there is many solutions for 0.078 and better. I would like to know, how it is possible?! best regards, Denis |
Some tests | Rustam Ganeyev | 1198. Коррупция | 3 дек 2010 19:30 | 2 |
Very good problem. Thx to autors! Some tests, that helped me to to solve that problem. 7 2 7 0 3 0 4 0 5 0 3 0 1 0 6 0 answer: 1 6 7 0 9 3 5 0 3 0 2 8 0 5 0 4 6 0 7 9 0 6 0 9 0 0 answer: 1 0 9 2 0 3 4 0 1 0 5 8 0 6 0 4 0 3 8 0 9 0 7 0 answer: 1 2 3 4 5 6 7 8 9 0 3 2 0 3 0 0 answer: 1 0 3 2 0 3 0 1 0 answer: 1 2 3 0 5 2 0 3 0 0 3 0 4 0 answer: 0 4 2 3 0 1 0 0 1 0 answer: 4 0 Edited by author 05.12.2009 04:56 |
if you have MLE | Ibragim Ismailov (TNU) | 1198. Коррупция | 27 ноя 2010 23:20 | 2 |
if you have MLE just change all int's to short's :) i use short and got AC in 0.453s && 15788kb and when i change adjacent list to "adjacent matrix" i Ac in 0.359s and 8044kb. sorry for my poor english. |
Weak tests | Alex Tolstov (Vologda STU) | 1198. Коррупция | 2 июл 2009 01:16 | 3 |
Weak tests Alex Tolstov (Vologda STU) 20 апр 2009 15:17 Hello! My AC solution can't pass this test: 8 2 3 0 1 3 0 1 2 4 0 5 6 0 4 6 0 1 4 5 0 5 0 3 0 Wrong Answer: 7 0 Correct Answer: 0 We added this test, but you are the only author who got WA on it. :) |
I solved this problem in 0.5s! | love_lq | 1198. Коррупция | 24 авг 2008 09:54 | 1 |
I used BFS only My hotmail is love_lq@hotmail.com Edited by author 24.08.2008 10:02 Edited by author 24.08.2008 10:02 |