# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
503071 |
2022-01-07T05:58:48 Z |
waynetuinfor |
Keys (IOI21_keys) |
C++17 |
|
1392 ms |
214276 KB |
#include <algorithm>
#include <cassert>
#include <functional>
#include <iostream>
#include <numeric>
#include <unordered_map>
#include <unordered_set>
#include <vector>
struct UnionFind {
UnionFind(int n) : uf(n) { std::iota(uf.begin(), uf.end(), 0); }
int Find(int x) {
if (x == uf[x]) return x;
return uf[x] = Find(uf[x]);
}
void Merge(int x, int y) {
int fx = Find(x), fy = Find(y);
uf[fx] = fy;
}
std::vector<int> uf;
};
std::vector<int> find_reachable(std::vector<int> r, std::vector<int> u,
std::vector<int> v, std::vector<int> c) {
int N = r.size(), M = u.size();
std::vector<std::unordered_set<int>> keys(N + N);
std::vector<std::unordered_map<int, std::vector<int>>> out_edges(N + N);
std::vector<std::vector<int>> good_edges(N + N);
std::vector<int> sz_v(N + N), sz_e(N + N);
std::vector<int> to(N + N, -1);
for (int i = 0; i < N; ++i) {
keys[i].insert(r[i]);
sz_v[i] = 1;
}
for (int i = 0; i < M; ++i) {
for (int x : {u[i], v[i]}) {
sz_e[x]++;
if (r[x] == c[i]) {
good_edges[x].push_back(i);
} else {
out_edges[x][c[i]].push_back(i);
}
}
}
int K = N;
UnionFind conn(N + N), repr(N + N);
std::vector<int> res;
for (int i = 0; i < K; ++i) {
while (!good_edges[i].empty()) {
int e = good_edges[i].back();
if (repr.Find(u[e]) == repr.Find(v[e])) {
good_edges[i].pop_back();
} else {
break;
}
}
if (good_edges[i].empty()) {
// std::cerr << "stop i = " << i << "\n";
res.push_back(i);
continue;
}
int e = good_edges[i].back();
int x = repr.Find(u[e]), y = repr.Find(v[e]);
assert(x == i || y == i);
if (x != i) {
std::swap(x, y);
}
// std::cerr << "x = " << x << " y = " << y << std::endl;
to[x] = y;
if (conn.Find(x) == conn.Find(y)) {
std::vector<int> cycle;
int t = i;
do {
// std::cerr << "t = " << t << std::endl;
cycle.push_back(t);
assert(to[t] != -1);
t = repr.Find(to[t]);
} while (t != i);
int p = K++;
for (int t : cycle) {
conn.Merge(t, p);
sz_v[p] += sz_v[t];
if (sz_e[p] < sz_e[t]) {
keys[p].swap(keys[t]);
out_edges[p].swap(out_edges[t]);
good_edges[p].swap(good_edges[t]);
}
sz_e[p] += sz_e[t];
good_edges[p].insert(good_edges[p].end(), good_edges[t].begin(),
good_edges[t].end());
for (int k : keys[t]) {
if (keys[p].find(k) == keys[p].end()) {
keys[p].insert(k);
if (out_edges[p].find(k) != out_edges[p].end()) {
good_edges[p].insert(good_edges[p].end(), out_edges[p][k].begin(),
out_edges[p][k].end());
out_edges[p].erase(k);
}
}
}
for (auto iter : out_edges[t]) {
int k = iter.first;
if (keys[p].find(k) != keys[p].end()) {
good_edges[p].insert(good_edges[p].end(), iter.second.begin(),
iter.second.end());
} else {
out_edges[p][k].insert(out_edges[p][k].end(), iter.second.begin(),
iter.second.end());
}
}
repr.Merge(t, p);
}
} else {
conn.Merge(x, y);
}
}
int min_sz = N + 1;
for (int u : res) {
assert(repr.Find(u) == u);
min_sz = std::min(min_sz, sz_v[u]);
}
std::vector<bool> opt(N + N);
for (int u : res) {
if (sz_v[u] == min_sz) {
opt[u] = true;
}
}
std::vector<int> ans(N);
for (int i = 0; i < N; ++i) {
if (opt[repr.Find(i)]) {
ans[i] = 1;
}
}
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
5 |
Correct |
0 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
0 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
332 KB |
Output is correct |
9 |
Correct |
1 ms |
288 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
5 |
Correct |
0 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
0 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
332 KB |
Output is correct |
9 |
Correct |
1 ms |
288 KB |
Output is correct |
10 |
Correct |
1 ms |
332 KB |
Output is correct |
11 |
Correct |
1 ms |
332 KB |
Output is correct |
12 |
Correct |
1 ms |
416 KB |
Output is correct |
13 |
Correct |
0 ms |
204 KB |
Output is correct |
14 |
Correct |
1 ms |
204 KB |
Output is correct |
15 |
Correct |
1 ms |
332 KB |
Output is correct |
16 |
Correct |
0 ms |
204 KB |
Output is correct |
17 |
Correct |
0 ms |
288 KB |
Output is correct |
18 |
Correct |
1 ms |
296 KB |
Output is correct |
19 |
Correct |
1 ms |
288 KB |
Output is correct |
20 |
Correct |
0 ms |
204 KB |
Output is correct |
21 |
Correct |
1 ms |
416 KB |
Output is correct |
22 |
Correct |
0 ms |
292 KB |
Output is correct |
23 |
Correct |
1 ms |
332 KB |
Output is correct |
24 |
Correct |
1 ms |
332 KB |
Output is correct |
25 |
Correct |
1 ms |
332 KB |
Output is correct |
26 |
Correct |
1 ms |
332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
5 |
Correct |
0 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
0 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
332 KB |
Output is correct |
9 |
Correct |
1 ms |
288 KB |
Output is correct |
10 |
Correct |
1 ms |
332 KB |
Output is correct |
11 |
Correct |
1 ms |
332 KB |
Output is correct |
12 |
Correct |
1 ms |
416 KB |
Output is correct |
13 |
Correct |
0 ms |
204 KB |
Output is correct |
14 |
Correct |
1 ms |
204 KB |
Output is correct |
15 |
Correct |
1 ms |
332 KB |
Output is correct |
16 |
Correct |
0 ms |
204 KB |
Output is correct |
17 |
Correct |
0 ms |
288 KB |
Output is correct |
18 |
Correct |
1 ms |
296 KB |
Output is correct |
19 |
Correct |
1 ms |
288 KB |
Output is correct |
20 |
Correct |
0 ms |
204 KB |
Output is correct |
21 |
Correct |
1 ms |
416 KB |
Output is correct |
22 |
Correct |
0 ms |
292 KB |
Output is correct |
23 |
Correct |
1 ms |
332 KB |
Output is correct |
24 |
Correct |
1 ms |
332 KB |
Output is correct |
25 |
Correct |
1 ms |
332 KB |
Output is correct |
26 |
Correct |
1 ms |
332 KB |
Output is correct |
27 |
Correct |
3 ms |
1740 KB |
Output is correct |
28 |
Correct |
3 ms |
1772 KB |
Output is correct |
29 |
Correct |
3 ms |
1768 KB |
Output is correct |
30 |
Correct |
2 ms |
844 KB |
Output is correct |
31 |
Correct |
1 ms |
972 KB |
Output is correct |
32 |
Correct |
1 ms |
460 KB |
Output is correct |
33 |
Correct |
2 ms |
844 KB |
Output is correct |
34 |
Correct |
1 ms |
940 KB |
Output is correct |
35 |
Correct |
2 ms |
844 KB |
Output is correct |
36 |
Correct |
3 ms |
1456 KB |
Output is correct |
37 |
Correct |
3 ms |
1484 KB |
Output is correct |
38 |
Correct |
3 ms |
1740 KB |
Output is correct |
39 |
Correct |
4 ms |
1712 KB |
Output is correct |
40 |
Correct |
2 ms |
972 KB |
Output is correct |
41 |
Correct |
3 ms |
1228 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
5 |
Correct |
0 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
0 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
332 KB |
Output is correct |
9 |
Correct |
1 ms |
288 KB |
Output is correct |
10 |
Correct |
657 ms |
104196 KB |
Output is correct |
11 |
Correct |
527 ms |
161316 KB |
Output is correct |
12 |
Correct |
162 ms |
38548 KB |
Output is correct |
13 |
Correct |
828 ms |
195824 KB |
Output is correct |
14 |
Correct |
273 ms |
167748 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
5 |
Correct |
0 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
0 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
332 KB |
Output is correct |
9 |
Correct |
1 ms |
288 KB |
Output is correct |
10 |
Correct |
1 ms |
332 KB |
Output is correct |
11 |
Correct |
1 ms |
332 KB |
Output is correct |
12 |
Correct |
1 ms |
416 KB |
Output is correct |
13 |
Correct |
0 ms |
204 KB |
Output is correct |
14 |
Correct |
1 ms |
204 KB |
Output is correct |
15 |
Correct |
1 ms |
332 KB |
Output is correct |
16 |
Correct |
0 ms |
204 KB |
Output is correct |
17 |
Correct |
0 ms |
288 KB |
Output is correct |
18 |
Correct |
1 ms |
296 KB |
Output is correct |
19 |
Correct |
1 ms |
288 KB |
Output is correct |
20 |
Correct |
0 ms |
204 KB |
Output is correct |
21 |
Correct |
1 ms |
416 KB |
Output is correct |
22 |
Correct |
0 ms |
292 KB |
Output is correct |
23 |
Correct |
1 ms |
332 KB |
Output is correct |
24 |
Correct |
1 ms |
332 KB |
Output is correct |
25 |
Correct |
1 ms |
332 KB |
Output is correct |
26 |
Correct |
1 ms |
332 KB |
Output is correct |
27 |
Correct |
3 ms |
1740 KB |
Output is correct |
28 |
Correct |
3 ms |
1772 KB |
Output is correct |
29 |
Correct |
3 ms |
1768 KB |
Output is correct |
30 |
Correct |
2 ms |
844 KB |
Output is correct |
31 |
Correct |
1 ms |
972 KB |
Output is correct |
32 |
Correct |
1 ms |
460 KB |
Output is correct |
33 |
Correct |
2 ms |
844 KB |
Output is correct |
34 |
Correct |
1 ms |
940 KB |
Output is correct |
35 |
Correct |
2 ms |
844 KB |
Output is correct |
36 |
Correct |
3 ms |
1456 KB |
Output is correct |
37 |
Correct |
3 ms |
1484 KB |
Output is correct |
38 |
Correct |
3 ms |
1740 KB |
Output is correct |
39 |
Correct |
4 ms |
1712 KB |
Output is correct |
40 |
Correct |
2 ms |
972 KB |
Output is correct |
41 |
Correct |
3 ms |
1228 KB |
Output is correct |
42 |
Correct |
657 ms |
104196 KB |
Output is correct |
43 |
Correct |
527 ms |
161316 KB |
Output is correct |
44 |
Correct |
162 ms |
38548 KB |
Output is correct |
45 |
Correct |
828 ms |
195824 KB |
Output is correct |
46 |
Correct |
273 ms |
167748 KB |
Output is correct |
47 |
Correct |
0 ms |
204 KB |
Output is correct |
48 |
Correct |
0 ms |
204 KB |
Output is correct |
49 |
Correct |
0 ms |
204 KB |
Output is correct |
50 |
Correct |
309 ms |
162320 KB |
Output is correct |
51 |
Correct |
347 ms |
164320 KB |
Output is correct |
52 |
Correct |
446 ms |
150708 KB |
Output is correct |
53 |
Correct |
486 ms |
150700 KB |
Output is correct |
54 |
Correct |
493 ms |
150596 KB |
Output is correct |
55 |
Correct |
738 ms |
114724 KB |
Output is correct |
56 |
Correct |
605 ms |
214276 KB |
Output is correct |
57 |
Correct |
514 ms |
212072 KB |
Output is correct |
58 |
Correct |
512 ms |
188308 KB |
Output is correct |
59 |
Correct |
988 ms |
169476 KB |
Output is correct |
60 |
Correct |
675 ms |
159396 KB |
Output is correct |
61 |
Correct |
877 ms |
171228 KB |
Output is correct |
62 |
Correct |
1392 ms |
187348 KB |
Output is correct |
63 |
Correct |
529 ms |
148964 KB |
Output is correct |
64 |
Correct |
5 ms |
3148 KB |
Output is correct |
65 |
Correct |
7 ms |
3104 KB |
Output is correct |
66 |
Correct |
1258 ms |
187204 KB |
Output is correct |
67 |
Correct |
28 ms |
17112 KB |
Output is correct |
68 |
Correct |
45 ms |
28092 KB |
Output is correct |
69 |
Correct |
973 ms |
169368 KB |
Output is correct |
70 |
Correct |
89 ms |
55856 KB |
Output is correct |
71 |
Correct |
268 ms |
168248 KB |
Output is correct |
72 |
Correct |
898 ms |
169360 KB |
Output is correct |
73 |
Correct |
1220 ms |
187172 KB |
Output is correct |