# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
435251 |
2021-06-23T06:16:34 Z |
ecnerwala |
Keys (IOI21_keys) |
C++17 |
|
1352 ms |
49712 KB |
#include "keys.h"
#include <bits/stdc++.h>
namespace ecnerwala {
struct par_compressor {
mutable std::vector<int> par;
par_compressor(int N) : par(N, -1) {}
int get_par(int a) const {
while (par[a] >= 0) {
if (par[par[a]] >= 0) par[a] = par[par[a]];
a = par[a];
}
return a;
}
void set_par(int a, int b) {
assert(par[a] < 0 && par[b] < 0);
assert(a != b);
par[b] += par[a];
par[a] = b;
}
int cc_sz(int a) const {
assert(par[a] < 0);
return -par[a];
}
};
}
std::vector<int> find_reachable(std::vector<int> R, std::vector<int> U, std::vector<int> V, std::vector<int> C) {
using namespace ecnerwala;
int N = int(R.size());
int M = int(U.size());
assert(M == int(V.size()));
assert(M == int(C.size()));
U.insert(U.end(), V.begin(), V.end());
V = {};
std::vector<int> edge_nxt(2*M, -1);
struct linked_list {
int st, en;
linked_list() : st(-1), en(-1) {}
explicit linked_list(int a) : st(a), en(a) {}
};
auto concat = [&](linked_list& a, linked_list& b) {
if (b.st == -1) return;
if (a.st == -1) {
a = b;
b.st = b.en = -1;
return;
}
edge_nxt[a.en] = b.st;
a.en = b.en;
b.st = b.en = -1;
};
struct treap_node {
std::array<int, 2> c = {-1, -1};
std::mt19937::result_type pri;
int v;
linked_list l;
};
using edge_set = int;
std::vector<treap_node> nodes(N+2*M);
std::mt19937 mt(std::chrono::steady_clock::now().time_since_epoch().count());
for (auto& n : nodes) n.pri = mt();
auto edge_set_union = [&](edge_set a_, edge_set b_, linked_list& unlocks) -> edge_set {
auto dfs = [&](auto self, edge_set a, edge_set b) -> edge_set {
if (b == -1) return a;
if (a == -1) return b;
if (nodes[a].pri > nodes[b].pri) std::swap(a, b);
// split b by a into x and y
int x, y;
{
int *l = &x, *r = &y;
while (true) {
if (b == -1) {
*l = *r = -1;
break;
}
if (nodes[b].v == nodes[a].v) {
if (nodes[b].l.st == -2) std::swap(nodes[a].l, nodes[b].l);
if (nodes[a].l.st == -2) {
if (nodes[b].l.st != -2) concat(unlocks, nodes[b].l);
} else {
concat(nodes[a].l, nodes[b].l);
}
*l = nodes[b].c[0];
*r = nodes[b].c[1];
break;
} else if (nodes[b].v < nodes[a].v) {
*l = b;
l = &nodes[b].c[1];
b = nodes[b].c[1];
} else if (nodes[b].v > nodes[a].v) {
*r = b;
r = &nodes[b].c[0];
b = nodes[b].c[0];
} else assert(false);
}
}
nodes[a].c[0] = self(self, nodes[a].c[0], x);
nodes[a].c[1] = self(self, nodes[a].c[1], y);
return a;
};
return dfs(dfs, a_, b_);
};
std::vector<linked_list> unlocked_edges(N);
std::vector<edge_set> locked_edges(N);
for (int i = 0; i < N; i++) {
locked_edges[i] = i;
nodes[i].v = R[i];
nodes[i].l = linked_list(-2);
}
for (int e = 0, o = M; e < 2*M; e++, o++) {
if (o == 2*M) o = 0;
int u = U[o];
int c = C[std::min(e, o)];
edge_set a = N+e;
nodes[a].v = c;
nodes[a].l = linked_list(e);
locked_edges[u] = edge_set_union(locked_edges[u], a, unlocked_edges[u]);
}
par_compressor compressed_node_par(N);
std::vector<int> forest_par(N, -1);
par_compressor forest_root(N);
int best_sz = N+1;
for (int st = 0; st < N; st++) {
while (true) {
int e = unlocked_edges[st].st;
if (e == -1) {
best_sz = std::min(best_sz, compressed_node_par.cc_sz(st));
break;
}
unlocked_edges[st].st = edge_nxt[e];
if (edge_nxt[e] == -1) unlocked_edges[st].en = -1;
edge_nxt[e] = -1;
int dest = compressed_node_par.get_par(U[e]);
int dest_tree = forest_root.get_par(dest);
if (dest_tree == st) {
// compress it
while (dest != st) {
// merge dest into st
concat(unlocked_edges[st], unlocked_edges[dest]);
locked_edges[st] = edge_set_union(locked_edges[st], locked_edges[dest], unlocked_edges[st]);
compressed_node_par.set_par(dest, st);
dest = compressed_node_par.get_par(forest_par[dest]);
}
} else {
// Link ourself up to dest and keep going
forest_par[st] = dest;
forest_root.set_par(st, dest_tree);
break;
}
}
}
std::vector<int> ans(N, false);
for (int i = 0; i < N; i++) {
int n = compressed_node_par.get_par(i);
if (forest_par[n] != -1) continue;
if (compressed_node_par.cc_sz(n) == best_sz) ans[i] = true;
}
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
1 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
1 ms |
204 KB |
Output is correct |
10 |
Correct |
1 ms |
204 KB |
Output is correct |
11 |
Correct |
1 ms |
204 KB |
Output is correct |
12 |
Correct |
1 ms |
204 KB |
Output is correct |
13 |
Correct |
1 ms |
204 KB |
Output is correct |
14 |
Correct |
1 ms |
204 KB |
Output is correct |
15 |
Correct |
1 ms |
204 KB |
Output is correct |
16 |
Correct |
1 ms |
204 KB |
Output is correct |
17 |
Correct |
1 ms |
204 KB |
Output is correct |
18 |
Correct |
1 ms |
204 KB |
Output is correct |
19 |
Correct |
1 ms |
204 KB |
Output is correct |
20 |
Correct |
1 ms |
204 KB |
Output is correct |
21 |
Correct |
1 ms |
204 KB |
Output is correct |
22 |
Correct |
1 ms |
204 KB |
Output is correct |
23 |
Correct |
1 ms |
204 KB |
Output is correct |
24 |
Correct |
1 ms |
204 KB |
Output is correct |
25 |
Correct |
1 ms |
204 KB |
Output is correct |
26 |
Correct |
1 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
1 ms |
204 KB |
Output is correct |
10 |
Correct |
1 ms |
204 KB |
Output is correct |
11 |
Correct |
1 ms |
204 KB |
Output is correct |
12 |
Correct |
1 ms |
204 KB |
Output is correct |
13 |
Correct |
1 ms |
204 KB |
Output is correct |
14 |
Correct |
1 ms |
204 KB |
Output is correct |
15 |
Correct |
1 ms |
204 KB |
Output is correct |
16 |
Correct |
1 ms |
204 KB |
Output is correct |
17 |
Correct |
1 ms |
204 KB |
Output is correct |
18 |
Correct |
1 ms |
204 KB |
Output is correct |
19 |
Correct |
1 ms |
204 KB |
Output is correct |
20 |
Correct |
1 ms |
204 KB |
Output is correct |
21 |
Correct |
1 ms |
204 KB |
Output is correct |
22 |
Correct |
1 ms |
204 KB |
Output is correct |
23 |
Correct |
1 ms |
204 KB |
Output is correct |
24 |
Correct |
1 ms |
204 KB |
Output is correct |
25 |
Correct |
1 ms |
204 KB |
Output is correct |
26 |
Correct |
1 ms |
204 KB |
Output is correct |
27 |
Correct |
2 ms |
588 KB |
Output is correct |
28 |
Correct |
2 ms |
588 KB |
Output is correct |
29 |
Correct |
2 ms |
588 KB |
Output is correct |
30 |
Correct |
2 ms |
332 KB |
Output is correct |
31 |
Correct |
1 ms |
332 KB |
Output is correct |
32 |
Correct |
1 ms |
332 KB |
Output is correct |
33 |
Correct |
1 ms |
332 KB |
Output is correct |
34 |
Correct |
1 ms |
332 KB |
Output is correct |
35 |
Correct |
2 ms |
332 KB |
Output is correct |
36 |
Correct |
2 ms |
588 KB |
Output is correct |
37 |
Correct |
3 ms |
588 KB |
Output is correct |
38 |
Correct |
4 ms |
588 KB |
Output is correct |
39 |
Correct |
3 ms |
588 KB |
Output is correct |
40 |
Correct |
2 ms |
460 KB |
Output is correct |
41 |
Correct |
3 ms |
460 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
1 ms |
204 KB |
Output is correct |
10 |
Correct |
453 ms |
36268 KB |
Output is correct |
11 |
Correct |
425 ms |
49524 KB |
Output is correct |
12 |
Correct |
55 ms |
9416 KB |
Output is correct |
13 |
Correct |
498 ms |
45660 KB |
Output is correct |
14 |
Correct |
205 ms |
49500 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
1 ms |
204 KB |
Output is correct |
10 |
Correct |
1 ms |
204 KB |
Output is correct |
11 |
Correct |
1 ms |
204 KB |
Output is correct |
12 |
Correct |
1 ms |
204 KB |
Output is correct |
13 |
Correct |
1 ms |
204 KB |
Output is correct |
14 |
Correct |
1 ms |
204 KB |
Output is correct |
15 |
Correct |
1 ms |
204 KB |
Output is correct |
16 |
Correct |
1 ms |
204 KB |
Output is correct |
17 |
Correct |
1 ms |
204 KB |
Output is correct |
18 |
Correct |
1 ms |
204 KB |
Output is correct |
19 |
Correct |
1 ms |
204 KB |
Output is correct |
20 |
Correct |
1 ms |
204 KB |
Output is correct |
21 |
Correct |
1 ms |
204 KB |
Output is correct |
22 |
Correct |
1 ms |
204 KB |
Output is correct |
23 |
Correct |
1 ms |
204 KB |
Output is correct |
24 |
Correct |
1 ms |
204 KB |
Output is correct |
25 |
Correct |
1 ms |
204 KB |
Output is correct |
26 |
Correct |
1 ms |
204 KB |
Output is correct |
27 |
Correct |
2 ms |
588 KB |
Output is correct |
28 |
Correct |
2 ms |
588 KB |
Output is correct |
29 |
Correct |
2 ms |
588 KB |
Output is correct |
30 |
Correct |
2 ms |
332 KB |
Output is correct |
31 |
Correct |
1 ms |
332 KB |
Output is correct |
32 |
Correct |
1 ms |
332 KB |
Output is correct |
33 |
Correct |
1 ms |
332 KB |
Output is correct |
34 |
Correct |
1 ms |
332 KB |
Output is correct |
35 |
Correct |
2 ms |
332 KB |
Output is correct |
36 |
Correct |
2 ms |
588 KB |
Output is correct |
37 |
Correct |
3 ms |
588 KB |
Output is correct |
38 |
Correct |
4 ms |
588 KB |
Output is correct |
39 |
Correct |
3 ms |
588 KB |
Output is correct |
40 |
Correct |
2 ms |
460 KB |
Output is correct |
41 |
Correct |
3 ms |
460 KB |
Output is correct |
42 |
Correct |
453 ms |
36268 KB |
Output is correct |
43 |
Correct |
425 ms |
49524 KB |
Output is correct |
44 |
Correct |
55 ms |
9416 KB |
Output is correct |
45 |
Correct |
498 ms |
45660 KB |
Output is correct |
46 |
Correct |
205 ms |
49500 KB |
Output is correct |
47 |
Correct |
1 ms |
204 KB |
Output is correct |
48 |
Correct |
1 ms |
204 KB |
Output is correct |
49 |
Correct |
1 ms |
204 KB |
Output is correct |
50 |
Correct |
238 ms |
49632 KB |
Output is correct |
51 |
Correct |
228 ms |
49712 KB |
Output is correct |
52 |
Correct |
237 ms |
33132 KB |
Output is correct |
53 |
Correct |
258 ms |
33084 KB |
Output is correct |
54 |
Correct |
251 ms |
33140 KB |
Output is correct |
55 |
Correct |
686 ms |
36292 KB |
Output is correct |
56 |
Correct |
427 ms |
49584 KB |
Output is correct |
57 |
Correct |
262 ms |
49628 KB |
Output is correct |
58 |
Correct |
861 ms |
49524 KB |
Output is correct |
59 |
Correct |
1255 ms |
42948 KB |
Output is correct |
60 |
Correct |
1116 ms |
43072 KB |
Output is correct |
61 |
Correct |
1058 ms |
42940 KB |
Output is correct |
62 |
Correct |
768 ms |
38372 KB |
Output is correct |
63 |
Correct |
221 ms |
40632 KB |
Output is correct |
64 |
Correct |
4 ms |
1100 KB |
Output is correct |
65 |
Correct |
4 ms |
1100 KB |
Output is correct |
66 |
Correct |
770 ms |
38368 KB |
Output is correct |
67 |
Correct |
28 ms |
5224 KB |
Output is correct |
68 |
Correct |
34 ms |
8432 KB |
Output is correct |
69 |
Correct |
1210 ms |
42944 KB |
Output is correct |
70 |
Correct |
81 ms |
16692 KB |
Output is correct |
71 |
Correct |
241 ms |
49516 KB |
Output is correct |
72 |
Correct |
1352 ms |
42948 KB |
Output is correct |
73 |
Correct |
852 ms |
38372 KB |
Output is correct |