# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
574603 |
2022-06-08T22:45:23 Z |
wjajjsasqq |
Keys (IOI21_keys) |
C++17 |
|
439 ms |
67624 KB |
#include "keys.h"
#include <cassert>
#include <cstdio>
#include <cstring>
#include <vector>
const int N = 300000;
int n, to[N], top[N], go[N], vis[N], size[N], from[N], wascol[N], was[N], leave[N], top1[N];
std::vector<std::pair<int, int> > g[N];
std::vector<int> unlock[N], t[N];
bool need[N];
int find(int v) {
if (top[v] == -1) return v;
return top[v] = find(top[v]);
}
int find1(int v) {
if (top1[v] == -1) return v;
return top1[v] = find1(top1[v]);
}
void merge(int a, int b) {
a = find(a);
b = find(b);
if (a != b) top[b] = a;
}
void dfs(int v, int x) {
if (from[v] != -1) return;
from[v] = x;
for (int i = 0; i < (int)t[v].size(); ++i) dfs(t[v][i], x);
}
std::vector<int> find_reachable(std::vector<int> r, std::vector<int> u, std::vector<int> v, std::vector<int> c) {
n = r.size();
for (int i = 0; i < n; ++i) to[i] = -1;
for (int i = 0; i < (int)u.size(); ++i) {
g[u[i]].push_back(std::make_pair(v[i], c[i]));
g[v[i]].push_back(std::make_pair(u[i], c[i]));
}
std::vector<int> ans(n);
bool any = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < (int)g[i].size(); ++j) if (g[i][j].second == r[i]) to[i] = g[i][j].first;
if (to[i] == -1) any = 1;
else t[to[i]].push_back(i);
}
if (any) {
for (int i = 0; i < n; ++i) if (to[i] == -1) ans[i] = 1;
return ans;
}
for (int i = 0; i < n; ++i) {
top[i] = top1[i] = -1;
need[i] = 1;
go[i] = to[i];
}
int it = 0;
do {
++it;
assert(it <= 20);
std::vector<int> ii;
memset(vis, 0, sizeof vis);
int it = 0;
for (int i = 0; i < n; ++i) if (need[i] && !vis[i] && top[i] == -1) {
++it;
int cur = i;
std::vector<int> vv;
while (!vis[cur]) {
vis[cur] = it;
vv.push_back(cur);
if (go[cur] == -1) break;
cur = go[cur];
if (go[cur] == -1) top1[i] = go[i];
}
if (vis[cur] == it) {
if (go[cur] == -1) ii.push_back(cur);
else {
int start = cur;
do {
merge(cur, go[cur]);
cur = go[cur];
} while (cur != start);
cur = find(cur);
ii.push_back(cur);
}
}
for (int i = 0; i < (int)vv.size(); ++i) if (vv[i] != cur) top1[vv[i]] = cur;
}
memset(need, 0, sizeof need);
for (int i = 0; i < (int)ii.size(); ++i) need[ii[i]] = 1;
for (int i = 0; i < n; ++i) from[i] = find1(i);
any = 0;
int dit = 0;
memset(was, 0, sizeof was);
memset(wascol, 0, sizeof wascol);
std::vector<int> total(n);
for (int i = 0; i < (int)ii.size(); ++i) {
++dit;
int start = ii[i];
std::vector<int> vec;
vec.push_back(start);
was[start] = dit;
int res = -1;
std::vector<int> cc;
while (!vec.empty() && res == -1) {
int v = vec.back();
vec.pop_back();
if (find(v) != start && need[find(v)]) res = find(v);
else if (from[v] != start) res = from[v];
else {
int c = r[v];
if (find(v) != start) top[find(v)] = start;
++total[v];
assert(total[v] < 2);
if (wascol[c] != dit) {
wascol[c] = dit;
for (int i = 0; i < (int)unlock[c].size(); ++i) if (was[unlock[c][i]] != dit) {
int next = unlock[c][i];
was[next] = dit;
vec.push_back(next);
}
}
if (res == -1) for (int i = 0; i < (int)g[v].size(); ++i) if (was[g[v][i].first] != dit) {
if (wascol[g[v][i].second] == dit) {
int next = g[v][i].first;
was[next] = dit;
vec.push_back(next);
} else {
cc.push_back(g[v][i].second);
unlock[g[v][i].second].push_back(g[v][i].first);
}
}
}
}
for (int i = 0; i < (int)cc.size(); ++i) unlock[cc[i]].clear();
go[start] = res;
if (res != -1) any = 1;
}
} while (any);
for (int i = 0; i < n; ++i) if (need[find(i)]) ++size[find(i)];
int mn = n;
for (int i = 0; i < n; ++i) if (need[i] && top[i] == -1) mn = std::min(mn, size[i]);
for (int i = 0; i < n; ++i) if (need[find(i)] && size[find(i)] == mn) ans[i] = 1;
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
25172 KB |
Output is correct |
2 |
Correct |
12 ms |
21332 KB |
Output is correct |
3 |
Correct |
12 ms |
21428 KB |
Output is correct |
4 |
Correct |
12 ms |
21448 KB |
Output is correct |
5 |
Correct |
12 ms |
25172 KB |
Output is correct |
6 |
Correct |
13 ms |
25184 KB |
Output is correct |
7 |
Correct |
13 ms |
25172 KB |
Output is correct |
8 |
Correct |
16 ms |
25172 KB |
Output is correct |
9 |
Correct |
11 ms |
21452 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
25172 KB |
Output is correct |
2 |
Correct |
12 ms |
21332 KB |
Output is correct |
3 |
Correct |
12 ms |
21428 KB |
Output is correct |
4 |
Correct |
12 ms |
21448 KB |
Output is correct |
5 |
Correct |
12 ms |
25172 KB |
Output is correct |
6 |
Correct |
13 ms |
25184 KB |
Output is correct |
7 |
Correct |
13 ms |
25172 KB |
Output is correct |
8 |
Correct |
16 ms |
25172 KB |
Output is correct |
9 |
Correct |
11 ms |
21452 KB |
Output is correct |
10 |
Correct |
10 ms |
21416 KB |
Output is correct |
11 |
Correct |
12 ms |
21376 KB |
Output is correct |
12 |
Correct |
12 ms |
21420 KB |
Output is correct |
13 |
Correct |
12 ms |
21404 KB |
Output is correct |
14 |
Correct |
10 ms |
21436 KB |
Output is correct |
15 |
Correct |
12 ms |
25172 KB |
Output is correct |
16 |
Correct |
13 ms |
25168 KB |
Output is correct |
17 |
Correct |
12 ms |
25172 KB |
Output is correct |
18 |
Correct |
13 ms |
25244 KB |
Output is correct |
19 |
Correct |
13 ms |
25264 KB |
Output is correct |
20 |
Correct |
15 ms |
25172 KB |
Output is correct |
21 |
Correct |
13 ms |
25264 KB |
Output is correct |
22 |
Correct |
14 ms |
21424 KB |
Output is correct |
23 |
Correct |
10 ms |
21332 KB |
Output is correct |
24 |
Correct |
11 ms |
21448 KB |
Output is correct |
25 |
Correct |
11 ms |
21392 KB |
Output is correct |
26 |
Correct |
13 ms |
21336 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
25172 KB |
Output is correct |
2 |
Correct |
12 ms |
21332 KB |
Output is correct |
3 |
Correct |
12 ms |
21428 KB |
Output is correct |
4 |
Correct |
12 ms |
21448 KB |
Output is correct |
5 |
Correct |
12 ms |
25172 KB |
Output is correct |
6 |
Correct |
13 ms |
25184 KB |
Output is correct |
7 |
Correct |
13 ms |
25172 KB |
Output is correct |
8 |
Correct |
16 ms |
25172 KB |
Output is correct |
9 |
Correct |
11 ms |
21452 KB |
Output is correct |
10 |
Correct |
10 ms |
21416 KB |
Output is correct |
11 |
Correct |
12 ms |
21376 KB |
Output is correct |
12 |
Correct |
12 ms |
21420 KB |
Output is correct |
13 |
Correct |
12 ms |
21404 KB |
Output is correct |
14 |
Correct |
10 ms |
21436 KB |
Output is correct |
15 |
Correct |
12 ms |
25172 KB |
Output is correct |
16 |
Correct |
13 ms |
25168 KB |
Output is correct |
17 |
Correct |
12 ms |
25172 KB |
Output is correct |
18 |
Correct |
13 ms |
25244 KB |
Output is correct |
19 |
Correct |
13 ms |
25264 KB |
Output is correct |
20 |
Correct |
15 ms |
25172 KB |
Output is correct |
21 |
Correct |
13 ms |
25264 KB |
Output is correct |
22 |
Correct |
14 ms |
21424 KB |
Output is correct |
23 |
Correct |
10 ms |
21332 KB |
Output is correct |
24 |
Correct |
11 ms |
21448 KB |
Output is correct |
25 |
Correct |
11 ms |
21392 KB |
Output is correct |
26 |
Correct |
13 ms |
21336 KB |
Output is correct |
27 |
Correct |
12 ms |
21588 KB |
Output is correct |
28 |
Correct |
12 ms |
21588 KB |
Output is correct |
29 |
Correct |
12 ms |
21588 KB |
Output is correct |
30 |
Correct |
12 ms |
25352 KB |
Output is correct |
31 |
Correct |
11 ms |
21460 KB |
Output is correct |
32 |
Correct |
15 ms |
25304 KB |
Output is correct |
33 |
Correct |
13 ms |
25316 KB |
Output is correct |
34 |
Correct |
13 ms |
25396 KB |
Output is correct |
35 |
Correct |
11 ms |
21588 KB |
Output is correct |
36 |
Correct |
16 ms |
21488 KB |
Output is correct |
37 |
Correct |
14 ms |
21588 KB |
Output is correct |
38 |
Correct |
13 ms |
21616 KB |
Output is correct |
39 |
Correct |
13 ms |
21560 KB |
Output is correct |
40 |
Correct |
14 ms |
25380 KB |
Output is correct |
41 |
Correct |
18 ms |
25428 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
25172 KB |
Output is correct |
2 |
Correct |
12 ms |
21332 KB |
Output is correct |
3 |
Correct |
12 ms |
21428 KB |
Output is correct |
4 |
Correct |
12 ms |
21448 KB |
Output is correct |
5 |
Correct |
12 ms |
25172 KB |
Output is correct |
6 |
Correct |
13 ms |
25184 KB |
Output is correct |
7 |
Correct |
13 ms |
25172 KB |
Output is correct |
8 |
Correct |
16 ms |
25172 KB |
Output is correct |
9 |
Correct |
11 ms |
21452 KB |
Output is correct |
10 |
Correct |
161 ms |
40316 KB |
Output is correct |
11 |
Correct |
230 ms |
58588 KB |
Output is correct |
12 |
Correct |
63 ms |
31976 KB |
Output is correct |
13 |
Correct |
439 ms |
59328 KB |
Output is correct |
14 |
Correct |
165 ms |
67024 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
25172 KB |
Output is correct |
2 |
Correct |
12 ms |
21332 KB |
Output is correct |
3 |
Correct |
12 ms |
21428 KB |
Output is correct |
4 |
Correct |
12 ms |
21448 KB |
Output is correct |
5 |
Correct |
12 ms |
25172 KB |
Output is correct |
6 |
Correct |
13 ms |
25184 KB |
Output is correct |
7 |
Correct |
13 ms |
25172 KB |
Output is correct |
8 |
Correct |
16 ms |
25172 KB |
Output is correct |
9 |
Correct |
11 ms |
21452 KB |
Output is correct |
10 |
Correct |
10 ms |
21416 KB |
Output is correct |
11 |
Correct |
12 ms |
21376 KB |
Output is correct |
12 |
Correct |
12 ms |
21420 KB |
Output is correct |
13 |
Correct |
12 ms |
21404 KB |
Output is correct |
14 |
Correct |
10 ms |
21436 KB |
Output is correct |
15 |
Correct |
12 ms |
25172 KB |
Output is correct |
16 |
Correct |
13 ms |
25168 KB |
Output is correct |
17 |
Correct |
12 ms |
25172 KB |
Output is correct |
18 |
Correct |
13 ms |
25244 KB |
Output is correct |
19 |
Correct |
13 ms |
25264 KB |
Output is correct |
20 |
Correct |
15 ms |
25172 KB |
Output is correct |
21 |
Correct |
13 ms |
25264 KB |
Output is correct |
22 |
Correct |
14 ms |
21424 KB |
Output is correct |
23 |
Correct |
10 ms |
21332 KB |
Output is correct |
24 |
Correct |
11 ms |
21448 KB |
Output is correct |
25 |
Correct |
11 ms |
21392 KB |
Output is correct |
26 |
Correct |
13 ms |
21336 KB |
Output is correct |
27 |
Correct |
12 ms |
21588 KB |
Output is correct |
28 |
Correct |
12 ms |
21588 KB |
Output is correct |
29 |
Correct |
12 ms |
21588 KB |
Output is correct |
30 |
Correct |
12 ms |
25352 KB |
Output is correct |
31 |
Correct |
11 ms |
21460 KB |
Output is correct |
32 |
Correct |
15 ms |
25304 KB |
Output is correct |
33 |
Correct |
13 ms |
25316 KB |
Output is correct |
34 |
Correct |
13 ms |
25396 KB |
Output is correct |
35 |
Correct |
11 ms |
21588 KB |
Output is correct |
36 |
Correct |
16 ms |
21488 KB |
Output is correct |
37 |
Correct |
14 ms |
21588 KB |
Output is correct |
38 |
Correct |
13 ms |
21616 KB |
Output is correct |
39 |
Correct |
13 ms |
21560 KB |
Output is correct |
40 |
Correct |
14 ms |
25380 KB |
Output is correct |
41 |
Correct |
18 ms |
25428 KB |
Output is correct |
42 |
Correct |
161 ms |
40316 KB |
Output is correct |
43 |
Correct |
230 ms |
58588 KB |
Output is correct |
44 |
Correct |
63 ms |
31976 KB |
Output is correct |
45 |
Correct |
439 ms |
59328 KB |
Output is correct |
46 |
Correct |
165 ms |
67024 KB |
Output is correct |
47 |
Correct |
15 ms |
25204 KB |
Output is correct |
48 |
Correct |
13 ms |
25248 KB |
Output is correct |
49 |
Correct |
11 ms |
21436 KB |
Output is correct |
50 |
Correct |
161 ms |
64692 KB |
Output is correct |
51 |
Correct |
160 ms |
58064 KB |
Output is correct |
52 |
Correct |
210 ms |
45280 KB |
Output is correct |
53 |
Correct |
175 ms |
45288 KB |
Output is correct |
54 |
Correct |
181 ms |
45240 KB |
Output is correct |
55 |
Correct |
180 ms |
45680 KB |
Output is correct |
56 |
Correct |
256 ms |
56268 KB |
Output is correct |
57 |
Correct |
182 ms |
52840 KB |
Output is correct |
58 |
Correct |
221 ms |
55912 KB |
Output is correct |
59 |
Correct |
368 ms |
64324 KB |
Output is correct |
60 |
Correct |
251 ms |
53596 KB |
Output is correct |
61 |
Correct |
293 ms |
53820 KB |
Output is correct |
62 |
Correct |
201 ms |
49292 KB |
Output is correct |
63 |
Correct |
177 ms |
61224 KB |
Output is correct |
64 |
Correct |
16 ms |
25940 KB |
Output is correct |
65 |
Correct |
18 ms |
25940 KB |
Output is correct |
66 |
Correct |
226 ms |
49432 KB |
Output is correct |
67 |
Correct |
27 ms |
29460 KB |
Output is correct |
68 |
Correct |
37 ms |
32140 KB |
Output is correct |
69 |
Correct |
337 ms |
64272 KB |
Output is correct |
70 |
Correct |
69 ms |
39236 KB |
Output is correct |
71 |
Correct |
196 ms |
67624 KB |
Output is correct |
72 |
Correct |
355 ms |
64252 KB |
Output is correct |
73 |
Correct |
229 ms |
49264 KB |
Output is correct |