|
|
but Kosaraju + scanf + MS compiler may help here 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 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 can anyone please share solution that works under 1 sec and under 10MB, I would really appreaciate it. my email is: ikhomeriki@gmail.com 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.. 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 The new time limit is 1.5 seconds. About 50 more authors have AC now, while a few have lost their AC 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...? 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. I got accepted in 0.78s using scanf instead of cin which makes me TLE 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 The complexity of the optimal algorithm is O(N + M), because the input is not O(N ^ 2) is O(M). is graph just full on 49 test? probably nop , cose i test prog on full 2000 less then .1sec 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. 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
Ну как? My program passed all these tests but still have WA12 :( 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 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 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. 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 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 |
|
|