# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
67513 | 2018-08-14T13:18:15 Z | zscoder | Toy Train (IOI17_train) | C++17 | 549 ms | 16764 KB |
#include "train.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef vector<int> vi; typedef pair<ll,ll> ii; #define mp make_pair #define pb push_back #define fi first #define se second vi adj[22222]; vi radj[22222]; std::vector<int> who_wins(std::vector<int> a, std::vector<int> r, std::vector<int> u, std::vector<int> v) { std::vector<int> res(a.size(),0); int n=res.size(); for(int i=0;i<u.size();i++) { adj[u[i]].pb(v[i]); radj[v[i]].pb(u[i]); } while(1) { vector<int> deg(n,0); vector<int> visited(n,0); for(int i=0;i<n;i++) deg[i]=adj[i].size(); queue<int> q; for(int i=0;i<n;i++){if(r[i]) q.push(i);} while(!q.empty()) { int u=q.front(); q.pop(); for(int v:radj[u]) { if(a[v]) { if(!visited[v]) { visited[v]=1; if(!r[v]) q.push(v); //or else double count for case 2 } } else { deg[v]--; if(!deg[v]) { if(!visited[v]) { visited[v]=1; if(!r[v]) q.push(v); } } } } } bool edit=0; for(int i=0;i<n;i++){if(r[i]&&!visited[i]) r[i]=0,edit=1;} if(edit) continue; res=visited; break; } return res; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 11 ms | 2040 KB | Output is correct |
2 | Correct | 19 ms | 2268 KB | Output is correct |
3 | Correct | 17 ms | 2296 KB | Output is correct |
4 | Correct | 17 ms | 2448 KB | Output is correct |
5 | Correct | 16 ms | 2596 KB | Output is correct |
6 | Correct | 15 ms | 2680 KB | Output is correct |
7 | Correct | 13 ms | 2836 KB | Output is correct |
8 | Correct | 13 ms | 3028 KB | Output is correct |
9 | Correct | 8 ms | 3096 KB | Output is correct |
10 | Correct | 8 ms | 3096 KB | Output is correct |
11 | Correct | 10 ms | 3148 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 3148 KB | Output is correct |
2 | Correct | 4 ms | 3148 KB | Output is correct |
3 | Correct | 4 ms | 3148 KB | Output is correct |
4 | Correct | 4 ms | 3148 KB | Output is correct |
5 | Correct | 3 ms | 3148 KB | Output is correct |
6 | Correct | 4 ms | 3148 KB | Output is correct |
7 | Correct | 5 ms | 3148 KB | Output is correct |
8 | Correct | 4 ms | 3148 KB | Output is correct |
9 | Correct | 4 ms | 3148 KB | Output is correct |
10 | Correct | 4 ms | 3148 KB | Output is correct |
11 | Correct | 3 ms | 3148 KB | Output is correct |
12 | Correct | 3 ms | 3148 KB | Output is correct |
13 | Correct | 3 ms | 3148 KB | Output is correct |
14 | Correct | 3 ms | 3148 KB | Output is correct |
15 | Correct | 2 ms | 3148 KB | Output is correct |
16 | Correct | 4 ms | 3148 KB | Output is correct |
17 | Correct | 4 ms | 3148 KB | Output is correct |
18 | Correct | 3 ms | 3148 KB | Output is correct |
19 | Correct | 3 ms | 3148 KB | Output is correct |
20 | Correct | 3 ms | 3148 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 85 ms | 3828 KB | Output is correct |
2 | Correct | 154 ms | 4164 KB | Output is correct |
3 | Correct | 195 ms | 4340 KB | Output is correct |
4 | Correct | 16 ms | 4452 KB | Output is correct |
5 | Correct | 18 ms | 4660 KB | Output is correct |
6 | Correct | 16 ms | 4868 KB | Output is correct |
7 | Correct | 14 ms | 5076 KB | Output is correct |
8 | Correct | 12 ms | 5284 KB | Output is correct |
9 | Correct | 14 ms | 5492 KB | Output is correct |
10 | Correct | 16 ms | 5768 KB | Output is correct |
11 | Correct | 14 ms | 5768 KB | Output is correct |
12 | Correct | 14 ms | 5944 KB | Output is correct |
13 | Correct | 13 ms | 6256 KB | Output is correct |
14 | Correct | 17 ms | 6464 KB | Output is correct |
15 | Correct | 14 ms | 6712 KB | Output is correct |
16 | Correct | 14 ms | 6880 KB | Output is correct |
17 | Correct | 15 ms | 7088 KB | Output is correct |
18 | Correct | 303 ms | 7088 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 15 ms | 7284 KB | Output is correct |
2 | Correct | 14 ms | 7444 KB | Output is correct |
3 | Correct | 14 ms | 7752 KB | Output is correct |
4 | Correct | 13 ms | 7960 KB | Output is correct |
5 | Correct | 15 ms | 8172 KB | Output is correct |
6 | Correct | 13 ms | 8448 KB | Output is correct |
7 | Correct | 14 ms | 8520 KB | Output is correct |
8 | Correct | 12 ms | 8772 KB | Output is correct |
9 | Correct | 15 ms | 8840 KB | Output is correct |
10 | Correct | 16 ms | 9152 KB | Output is correct |
11 | Correct | 15 ms | 9360 KB | Output is correct |
12 | Correct | 15 ms | 9732 KB | Output is correct |
13 | Correct | 13 ms | 9780 KB | Output is correct |
14 | Correct | 17 ms | 9860 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 18 ms | 10176 KB | Output is correct |
2 | Correct | 17 ms | 10384 KB | Output is correct |
3 | Correct | 15 ms | 10592 KB | Output is correct |
4 | Correct | 13 ms | 10728 KB | Output is correct |
5 | Correct | 4 ms | 10728 KB | Output is correct |
6 | Correct | 10 ms | 10728 KB | Output is correct |
7 | Correct | 9 ms | 10728 KB | Output is correct |
8 | Correct | 9 ms | 10832 KB | Output is correct |
9 | Correct | 10 ms | 10984 KB | Output is correct |
10 | Correct | 5 ms | 10984 KB | Output is correct |
11 | Correct | 9 ms | 11156 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 11 ms | 2040 KB | Output is correct |
2 | Correct | 19 ms | 2268 KB | Output is correct |
3 | Correct | 17 ms | 2296 KB | Output is correct |
4 | Correct | 17 ms | 2448 KB | Output is correct |
5 | Correct | 16 ms | 2596 KB | Output is correct |
6 | Correct | 15 ms | 2680 KB | Output is correct |
7 | Correct | 13 ms | 2836 KB | Output is correct |
8 | Correct | 13 ms | 3028 KB | Output is correct |
9 | Correct | 8 ms | 3096 KB | Output is correct |
10 | Correct | 8 ms | 3096 KB | Output is correct |
11 | Correct | 10 ms | 3148 KB | Output is correct |
12 | Correct | 4 ms | 3148 KB | Output is correct |
13 | Correct | 4 ms | 3148 KB | Output is correct |
14 | Correct | 4 ms | 3148 KB | Output is correct |
15 | Correct | 4 ms | 3148 KB | Output is correct |
16 | Correct | 3 ms | 3148 KB | Output is correct |
17 | Correct | 4 ms | 3148 KB | Output is correct |
18 | Correct | 5 ms | 3148 KB | Output is correct |
19 | Correct | 4 ms | 3148 KB | Output is correct |
20 | Correct | 4 ms | 3148 KB | Output is correct |
21 | Correct | 4 ms | 3148 KB | Output is correct |
22 | Correct | 3 ms | 3148 KB | Output is correct |
23 | Correct | 3 ms | 3148 KB | Output is correct |
24 | Correct | 3 ms | 3148 KB | Output is correct |
25 | Correct | 3 ms | 3148 KB | Output is correct |
26 | Correct | 2 ms | 3148 KB | Output is correct |
27 | Correct | 4 ms | 3148 KB | Output is correct |
28 | Correct | 4 ms | 3148 KB | Output is correct |
29 | Correct | 3 ms | 3148 KB | Output is correct |
30 | Correct | 3 ms | 3148 KB | Output is correct |
31 | Correct | 3 ms | 3148 KB | Output is correct |
32 | Correct | 85 ms | 3828 KB | Output is correct |
33 | Correct | 154 ms | 4164 KB | Output is correct |
34 | Correct | 195 ms | 4340 KB | Output is correct |
35 | Correct | 16 ms | 4452 KB | Output is correct |
36 | Correct | 18 ms | 4660 KB | Output is correct |
37 | Correct | 16 ms | 4868 KB | Output is correct |
38 | Correct | 14 ms | 5076 KB | Output is correct |
39 | Correct | 12 ms | 5284 KB | Output is correct |
40 | Correct | 14 ms | 5492 KB | Output is correct |
41 | Correct | 16 ms | 5768 KB | Output is correct |
42 | Correct | 14 ms | 5768 KB | Output is correct |
43 | Correct | 14 ms | 5944 KB | Output is correct |
44 | Correct | 13 ms | 6256 KB | Output is correct |
45 | Correct | 17 ms | 6464 KB | Output is correct |
46 | Correct | 14 ms | 6712 KB | Output is correct |
47 | Correct | 14 ms | 6880 KB | Output is correct |
48 | Correct | 15 ms | 7088 KB | Output is correct |
49 | Correct | 303 ms | 7088 KB | Output is correct |
50 | Correct | 15 ms | 7284 KB | Output is correct |
51 | Correct | 14 ms | 7444 KB | Output is correct |
52 | Correct | 14 ms | 7752 KB | Output is correct |
53 | Correct | 13 ms | 7960 KB | Output is correct |
54 | Correct | 15 ms | 8172 KB | Output is correct |
55 | Correct | 13 ms | 8448 KB | Output is correct |
56 | Correct | 14 ms | 8520 KB | Output is correct |
57 | Correct | 12 ms | 8772 KB | Output is correct |
58 | Correct | 15 ms | 8840 KB | Output is correct |
59 | Correct | 16 ms | 9152 KB | Output is correct |
60 | Correct | 15 ms | 9360 KB | Output is correct |
61 | Correct | 15 ms | 9732 KB | Output is correct |
62 | Correct | 13 ms | 9780 KB | Output is correct |
63 | Correct | 17 ms | 9860 KB | Output is correct |
64 | Correct | 18 ms | 10176 KB | Output is correct |
65 | Correct | 17 ms | 10384 KB | Output is correct |
66 | Correct | 15 ms | 10592 KB | Output is correct |
67 | Correct | 13 ms | 10728 KB | Output is correct |
68 | Correct | 4 ms | 10728 KB | Output is correct |
69 | Correct | 10 ms | 10728 KB | Output is correct |
70 | Correct | 9 ms | 10728 KB | Output is correct |
71 | Correct | 9 ms | 10832 KB | Output is correct |
72 | Correct | 10 ms | 10984 KB | Output is correct |
73 | Correct | 5 ms | 10984 KB | Output is correct |
74 | Correct | 9 ms | 11156 KB | Output is correct |
75 | Correct | 118 ms | 11748 KB | Output is correct |
76 | Correct | 168 ms | 11972 KB | Output is correct |
77 | Correct | 206 ms | 12052 KB | Output is correct |
78 | Correct | 225 ms | 12360 KB | Output is correct |
79 | Correct | 235 ms | 12468 KB | Output is correct |
80 | Correct | 13 ms | 12676 KB | Output is correct |
81 | Correct | 16 ms | 12940 KB | Output is correct |
82 | Correct | 16 ms | 13084 KB | Output is correct |
83 | Correct | 23 ms | 13300 KB | Output is correct |
84 | Correct | 19 ms | 13508 KB | Output is correct |
85 | Correct | 15 ms | 13768 KB | Output is correct |
86 | Correct | 19 ms | 13940 KB | Output is correct |
87 | Correct | 13 ms | 14132 KB | Output is correct |
88 | Correct | 20 ms | 14340 KB | Output is correct |
89 | Correct | 14 ms | 14548 KB | Output is correct |
90 | Correct | 35 ms | 14820 KB | Output is correct |
91 | Correct | 28 ms | 14964 KB | Output is correct |
92 | Correct | 44 ms | 15172 KB | Output is correct |
93 | Correct | 38 ms | 15380 KB | Output is correct |
94 | Correct | 52 ms | 15592 KB | Output is correct |
95 | Correct | 48 ms | 15800 KB | Output is correct |
96 | Correct | 94 ms | 16040 KB | Output is correct |
97 | Correct | 327 ms | 16324 KB | Output is correct |
98 | Correct | 549 ms | 16472 KB | Output is correct |
99 | Correct | 546 ms | 16764 KB | Output is correct |
100 | Correct | 314 ms | 16764 KB | Output is correct |