Show all threads Hide all threads Show all messages Hide all messages |
TLE is a problem | goodcoffee | 1198. Jobbery | 26 Apr 2023 04:50 | 1 |
but Kosaraju + scanf + MS compiler may help here |
If you have TL 50 or ML 50 | andreyDagger | 1198. Jobbery | 25 Jan 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. Jobbery | 7 Aug 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. Jobbery | 16 Sep 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. Jobbery | 7 Dec 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. Jobbery | 28 Jul 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. Jobbery | 4 Feb 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. Jobbery | 25 Dec 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. Jobbery | 13 Nov 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. Jobbery | 7 Nov 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. Jobbery | 10 Aug 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. Jobbery | 5 Jan 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. Jobbery | 13 Aug 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. Jobbery | 25 Jul 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. Jobbery | 27 Apr 2012 14:08 | 6 |
WA 12 THE_SCORPION 4 May 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 Jul 2011 22:29 My program passed all these tests but still have WA12 :( Re: WA 12 Tbilisi SU: Dolidze Alexander 27 Apr 2012 14:08 |
fast solution | Denis Tapyshpan | 1198. Jobbery | 2 Dec 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. Jobbery | 3 Dec 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. Jobbery | 27 Nov 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. Jobbery | 2 Jul 2009 01:16 | 3 |
Weak tests Alex Tolstov (Vologda STU) 20 Apr 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. Jobbery | 24 Aug 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 |