Task: | Factory |
Sender: | kyy-kol |
Submission time: | 2017-05-27 11:46:10 +0300 |
Language: | C++ |
Status: | READY |
Result: | TIME LIMIT EXCEEDED |
test | verdict | time | |
---|---|---|---|
#1 | ACCEPTED | 0.04 s | details |
#2 | ACCEPTED | 0.04 s | details |
#3 | ACCEPTED | 0.04 s | details |
#4 | ACCEPTED | 0.04 s | details |
#5 | TIME LIMIT EXCEEDED | -- | details |
#6 | TIME LIMIT EXCEEDED | -- | details |
#7 | TIME LIMIT EXCEEDED | -- | details |
#8 | TIME LIMIT EXCEEDED | -- | details |
#9 | TIME LIMIT EXCEEDED | -- | details |
#10 | TIME LIMIT EXCEEDED | -- | details |
#11 | TIME LIMIT EXCEEDED | -- | details |
#12 | TIME LIMIT EXCEEDED | -- | details |
#13 | TIME LIMIT EXCEEDED | -- | details |
#14 | TIME LIMIT EXCEEDED | -- | details |
#15 | TIME LIMIT EXCEEDED | -- | details |
#16 | WRONG ANSWER | 0.06 s | details |
#17 | WRONG ANSWER | 0.04 s | details |
Compiler report
input/code.cpp: In function 'int main()': input/code.cpp:47:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare] for (int i = 0; i < ts.size(); ++i) { ^
Code
#include <iostream>#include <vector>#include <set>#include <algorithm>using namespace std;typedef vector<int> vi;#define PB push_backint n, m;vi g[505];vi ts;int v1[505];int comp[505];vector<int> cws;void dfs1(int s) {if (v1[s]) return;v1[s] = 1;for (int a : g[s]) {dfs1(a);}ts.push_back(s);}void dfs2(int s, int cc) {if (comp[s]) return;comp[s] = cc;for (int a : g[s]) {dfs2(a, cc);}}int main() {cin >> n >> m;for (int i = 0; i < m; ++i) {int a, b;cin >> a >> b;g[a].push_back(b);}for (int i = 1; i <= n; ++i) dfs1(i);reverse(ts.begin(), ts.end());int ccomp = 0;for (int i = 0; i < ts.size(); ++i) {int cur = ts[i];if (comp[cur] == 0) {ccomp++;dfs2(cur, ccomp);cws.PB(cur);}}int res = 0;while (cws.size() != 0) {int c1 = cws[cws.size()-1];cws.pop_back();int c2 = -1;if (cws.size() != 0) {c2 = cws[cws.size()-1];cws.pop_back();}res++;for (int a : g[c1]) {cws.PB(a);}if (c2 != -1) {for (int b : g[c2]) {cws.PB(b);}}}cout << res << "\n";return 0;}
Test details
Test 1
Verdict: ACCEPTED
input |
---|
1 0 |
correct output |
---|
1 |
user output |
---|
1 |
Test 2
Verdict: ACCEPTED
input |
---|
2 0 |
correct output |
---|
1 |
user output |
---|
1 |
Test 3
Verdict: ACCEPTED
input |
---|
2 1 2 1 |
correct output |
---|
2 |
user output |
---|
2 |
Test 4
Verdict: ACCEPTED
input |
---|
500 0 |
correct output |
---|
250 |
user output |
---|
250 |
Test 5
Verdict: TIME LIMIT EXCEEDED
input |
---|
500 124750 66 104 50 159 173 457 200 154 ... |
correct output |
---|
500 |
user output |
---|
(empty) |
Test 6
Verdict: TIME LIMIT EXCEEDED
input |
---|
500 96771 376 390 243 497 417 360 107 80 ... |
correct output |
---|
413 |
user output |
---|
(empty) |
Test 7
Verdict: TIME LIMIT EXCEEDED
input |
---|
500 106799 96 245 68 62 122 119 460 454 ... |
correct output |
---|
433 |
user output |
---|
(empty) |
Test 8
Verdict: TIME LIMIT EXCEEDED
input |
---|
500 83550 76 338 111 174 88 142 114 463 ... |
correct output |
---|
365 |
user output |
---|
(empty) |
Test 9
Verdict: TIME LIMIT EXCEEDED
input |
---|
500 98051 281 60 312 284 270 474 385 224 ... |
correct output |
---|
410 |
user output |
---|
(empty) |
Test 10
Verdict: TIME LIMIT EXCEEDED
input |
---|
500 86622 5 320 50 107 182 483 385 500 ... |
correct output |
---|
372 |
user output |
---|
(empty) |
Test 11
Verdict: TIME LIMIT EXCEEDED
input |
---|
500 99445 421 286 392 406 155 290 475 453 ... |
correct output |
---|
396 |
user output |
---|
(empty) |
Test 12
Verdict: TIME LIMIT EXCEEDED
input |
---|
500 99832 283 149 315 396 264 422 224 388 ... |
correct output |
---|
410 |
user output |
---|
(empty) |
Test 13
Verdict: TIME LIMIT EXCEEDED
input |
---|
500 116149 446 185 232 35 498 391 189 63 ... |
correct output |
---|
457 |
user output |
---|
(empty) |
Test 14
Verdict: TIME LIMIT EXCEEDED
input |
---|
500 84757 71 205 286 360 184 486 30 228 ... |
correct output |
---|
364 |
user output |
---|
(empty) |
Test 15
Verdict: TIME LIMIT EXCEEDED
input |
---|
500 108617 126 250 76 224 449 69 200 63 ... |
correct output |
---|
439 |
user output |
---|
(empty) |
Test 16
Verdict: WRONG ANSWER
input |
---|
10 20 7 8 1 3 4 8 5 9 ... |
correct output |
---|
5 |
user output |
---|
21 |
Test 17
Verdict: WRONG ANSWER
input |
---|
10 20 2 9 9 8 4 3 7 3 ... |
correct output |
---|
5 |
user output |
---|
19 |