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.

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 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?

Why? What is a key point of this task?

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?

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 :)

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

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