# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
518688 |
2022-01-24T12:27:40 Z |
fleimgruber |
Keys (IOI21_keys) |
C++17 |
|
1179 ms |
102704 KB |
// --- algolib/union-find.h ---
// union find, optionally with tags for each component. this is useful
// for example when compressing components. enable using template parameter
#include <algorithm>
#include <type_traits>
#include <numeric>
#include <vector>
template<typename T = void, typename enable = void>
class UnionFind {
std::vector<int> p, size_;
public:
UnionFind(int n = 0) : p(n), size_(n, 1) {
std::iota(p.begin(), p.end(), 0);
}
int create() {
int r = p.size();
p.push_back(r);
size_.push_back(1);
return r;
}
int find(int i) {
if (i == p[i])
return i;
return p[i] = find(p[i]);
}
int operator[](int i) { return find(i); }
int size(int i) { return size_[find(i)]; }
bool connected(int a, int b) { return find(a) == find(b); }
bool connect(int a, int b) {
a = find(a), b = find(b);
if (a == b)
return false;
if (size_[a] > size_[b])
std::swap(a, b);
size_[b] += size_[a];
p[a] = b;
return true;
}
};
// connect(a, b) maintains tag(b)
template<typename T>
class UnionFind<T, typename std::enable_if_t<!std::is_same_v<T, void>>>
: public UnionFind<void> {
std::vector<T> tags;
public:
UnionFind(int n = 0) : UnionFind<void>(n), tags(n) { }
void create() {
UnionFind<void>::create();
tags.emplace_back();
}
bool connect(int a, int b) {
T old = tag(b);
bool res = UnionFind<void>::connect(a, b);
set_tag(b, old);
return res;
}
void set_tag(int i, const T& t) { tags[find(i)] = t; }
const T& tag(int i) { return tags[find(i)]; }
};
// ----------------
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 300005;
int n;
vector<int> ans;
struct Edge {
int to, key; // key required
bool operator<(const Edge& o) const {
// cannot just use key, otherwise edges get lost (set)
return tie(key, to) < tie(o.key, o.to);
}
};
vector<int> out_can[MAX_N]; // only the to
set<Edge> out_blocked[MAX_N];
set<int> keys[MAX_N];
int par[MAX_N]; // parent in tree
UnionFind weakly(MAX_N); // weakly connected components
UnionFind<int> compressed(MAX_N);
// merge i into j, smaller to larger style
void merge(int i, int j) {
if (compressed.size(i) > compressed.size(j)) {
out_can[i].swap(out_can[j]);
out_blocked[i].swap(out_blocked[j]);
keys[i].swap(keys[j]);
}
compressed.connect(i, j); // tag of j is maintained
out_can[j].insert(out_can[j].end(),
out_can[i].begin(), out_can[i].end());
out_can[i].clear();
for (int key : keys[i])
if (keys[j].insert(key).second) { // promote
auto it = out_blocked[j].lower_bound({ -1, key });
while (it != out_blocked[j].end() && it->key == key) {
out_can[j].push_back(it->to);
it = out_blocked[j].erase(it);
}
}
keys[i].clear();
for (auto& x : out_blocked[i])
if (keys[j].find(x.key) == keys[j].end())
out_blocked[j].insert(x);
else if (!compressed.connected(j, x.to)) // pruning back edges
out_can[j].push_back(x.to);
out_blocked[i].clear();
return;
}
void solve() {
using pq_key = pair<int, int>; // size, vertex (roots order by size)
priority_queue<pq_key, vector<pq_key>, greater<pq_key>> roots;
// tags are the representatives (where keys & edges are stored)
for (int i = 0; i < n; i++) {
compressed.set_tag(i, i);
roots.push({ 1, i });
}
// != -1 means we already found an answer of size done_size
// so stop pushing to pq, but collect remaining components
int done_size = -1;
ans.assign(n, 0);
while (!roots.empty()) {
auto [_, r] = roots.top();
roots.pop();
// find any outgoing edge
bool has_outgoing = false;
while (!out_can[r].empty()) {
int to = out_can[r].back();
out_can[r].pop_back();
if (compressed.connected(r, to))
continue;
has_outgoing = true;
if (done_size != -1) // we're larger than the answer
break;
if (weakly.connected(r, to)) {
// merge with self. walk up parents
int j = compressed.tag(to);
do {
int jp = compressed.tag(par[j]);
merge(j, jp);
j = jp;
} while (j != r);
// we're still a root, but of larger size
roots.push({ compressed.size(r), r });
} else { // merge with other component
par[r] = to;
weakly.connect(r, to);
// we're no root any longer (no pq push)
}
break;
}
if (!has_outgoing) {
int size = compressed.size(r);
if (done_size != -1 && size != done_size)
break;
done_size = size;
ans[r] = 1;
}
}
for (int i = 0; i < n; i++) // everthing in their components too
if (ans[compressed.tag(i)])
ans[i] = 1;
}
vector<int> find_reachable(vector<int> r, vector<int> u,
vector<int> v, vector<int> c) {
n = r.size();
for (int i = 0; i < n; i++)
keys[i].insert(r[i]);
for (size_t i = 0; i < u.size(); i++)
for (int x = 0; x < 2; x++) {
if (r[u[i]] == c[i])
out_can[u[i]].push_back(v[i]);
else
out_blocked[u[i]].insert({ v[i], c[i] });
swap(u[i], v[i]);
}
solve();
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
20 ms |
41292 KB |
Output is correct |
2 |
Correct |
20 ms |
41328 KB |
Output is correct |
3 |
Correct |
25 ms |
41308 KB |
Output is correct |
4 |
Correct |
20 ms |
41376 KB |
Output is correct |
5 |
Correct |
19 ms |
41292 KB |
Output is correct |
6 |
Correct |
20 ms |
41292 KB |
Output is correct |
7 |
Correct |
20 ms |
41396 KB |
Output is correct |
8 |
Correct |
20 ms |
41352 KB |
Output is correct |
9 |
Correct |
19 ms |
41420 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
20 ms |
41292 KB |
Output is correct |
2 |
Correct |
20 ms |
41328 KB |
Output is correct |
3 |
Correct |
25 ms |
41308 KB |
Output is correct |
4 |
Correct |
20 ms |
41376 KB |
Output is correct |
5 |
Correct |
19 ms |
41292 KB |
Output is correct |
6 |
Correct |
20 ms |
41292 KB |
Output is correct |
7 |
Correct |
20 ms |
41396 KB |
Output is correct |
8 |
Correct |
20 ms |
41352 KB |
Output is correct |
9 |
Correct |
19 ms |
41420 KB |
Output is correct |
10 |
Correct |
21 ms |
41412 KB |
Output is correct |
11 |
Correct |
26 ms |
41364 KB |
Output is correct |
12 |
Correct |
21 ms |
41340 KB |
Output is correct |
13 |
Correct |
20 ms |
41292 KB |
Output is correct |
14 |
Correct |
20 ms |
41292 KB |
Output is correct |
15 |
Correct |
21 ms |
41404 KB |
Output is correct |
16 |
Correct |
22 ms |
41384 KB |
Output is correct |
17 |
Correct |
21 ms |
41404 KB |
Output is correct |
18 |
Correct |
19 ms |
41400 KB |
Output is correct |
19 |
Correct |
28 ms |
41292 KB |
Output is correct |
20 |
Correct |
23 ms |
41328 KB |
Output is correct |
21 |
Correct |
26 ms |
41336 KB |
Output is correct |
22 |
Correct |
22 ms |
41356 KB |
Output is correct |
23 |
Correct |
21 ms |
41380 KB |
Output is correct |
24 |
Correct |
21 ms |
41420 KB |
Output is correct |
25 |
Correct |
20 ms |
41388 KB |
Output is correct |
26 |
Correct |
20 ms |
41380 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
20 ms |
41292 KB |
Output is correct |
2 |
Correct |
20 ms |
41328 KB |
Output is correct |
3 |
Correct |
25 ms |
41308 KB |
Output is correct |
4 |
Correct |
20 ms |
41376 KB |
Output is correct |
5 |
Correct |
19 ms |
41292 KB |
Output is correct |
6 |
Correct |
20 ms |
41292 KB |
Output is correct |
7 |
Correct |
20 ms |
41396 KB |
Output is correct |
8 |
Correct |
20 ms |
41352 KB |
Output is correct |
9 |
Correct |
19 ms |
41420 KB |
Output is correct |
10 |
Correct |
21 ms |
41412 KB |
Output is correct |
11 |
Correct |
26 ms |
41364 KB |
Output is correct |
12 |
Correct |
21 ms |
41340 KB |
Output is correct |
13 |
Correct |
20 ms |
41292 KB |
Output is correct |
14 |
Correct |
20 ms |
41292 KB |
Output is correct |
15 |
Correct |
21 ms |
41404 KB |
Output is correct |
16 |
Correct |
22 ms |
41384 KB |
Output is correct |
17 |
Correct |
21 ms |
41404 KB |
Output is correct |
18 |
Correct |
19 ms |
41400 KB |
Output is correct |
19 |
Correct |
28 ms |
41292 KB |
Output is correct |
20 |
Correct |
23 ms |
41328 KB |
Output is correct |
21 |
Correct |
26 ms |
41336 KB |
Output is correct |
22 |
Correct |
22 ms |
41356 KB |
Output is correct |
23 |
Correct |
21 ms |
41380 KB |
Output is correct |
24 |
Correct |
21 ms |
41420 KB |
Output is correct |
25 |
Correct |
20 ms |
41388 KB |
Output is correct |
26 |
Correct |
20 ms |
41380 KB |
Output is correct |
27 |
Correct |
25 ms |
41668 KB |
Output is correct |
28 |
Correct |
23 ms |
41804 KB |
Output is correct |
29 |
Correct |
22 ms |
41672 KB |
Output is correct |
30 |
Correct |
22 ms |
41524 KB |
Output is correct |
31 |
Correct |
21 ms |
41504 KB |
Output is correct |
32 |
Correct |
20 ms |
41420 KB |
Output is correct |
33 |
Correct |
22 ms |
41532 KB |
Output is correct |
34 |
Correct |
22 ms |
41452 KB |
Output is correct |
35 |
Correct |
22 ms |
41540 KB |
Output is correct |
36 |
Correct |
21 ms |
41692 KB |
Output is correct |
37 |
Correct |
22 ms |
41676 KB |
Output is correct |
38 |
Correct |
22 ms |
41656 KB |
Output is correct |
39 |
Correct |
24 ms |
41772 KB |
Output is correct |
40 |
Correct |
22 ms |
41520 KB |
Output is correct |
41 |
Correct |
23 ms |
41676 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
20 ms |
41292 KB |
Output is correct |
2 |
Correct |
20 ms |
41328 KB |
Output is correct |
3 |
Correct |
25 ms |
41308 KB |
Output is correct |
4 |
Correct |
20 ms |
41376 KB |
Output is correct |
5 |
Correct |
19 ms |
41292 KB |
Output is correct |
6 |
Correct |
20 ms |
41292 KB |
Output is correct |
7 |
Correct |
20 ms |
41396 KB |
Output is correct |
8 |
Correct |
20 ms |
41352 KB |
Output is correct |
9 |
Correct |
19 ms |
41420 KB |
Output is correct |
10 |
Correct |
459 ms |
81720 KB |
Output is correct |
11 |
Correct |
727 ms |
102704 KB |
Output is correct |
12 |
Correct |
102 ms |
51136 KB |
Output is correct |
13 |
Correct |
588 ms |
88708 KB |
Output is correct |
14 |
Correct |
231 ms |
87084 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
20 ms |
41292 KB |
Output is correct |
2 |
Correct |
20 ms |
41328 KB |
Output is correct |
3 |
Correct |
25 ms |
41308 KB |
Output is correct |
4 |
Correct |
20 ms |
41376 KB |
Output is correct |
5 |
Correct |
19 ms |
41292 KB |
Output is correct |
6 |
Correct |
20 ms |
41292 KB |
Output is correct |
7 |
Correct |
20 ms |
41396 KB |
Output is correct |
8 |
Correct |
20 ms |
41352 KB |
Output is correct |
9 |
Correct |
19 ms |
41420 KB |
Output is correct |
10 |
Correct |
21 ms |
41412 KB |
Output is correct |
11 |
Correct |
26 ms |
41364 KB |
Output is correct |
12 |
Correct |
21 ms |
41340 KB |
Output is correct |
13 |
Correct |
20 ms |
41292 KB |
Output is correct |
14 |
Correct |
20 ms |
41292 KB |
Output is correct |
15 |
Correct |
21 ms |
41404 KB |
Output is correct |
16 |
Correct |
22 ms |
41384 KB |
Output is correct |
17 |
Correct |
21 ms |
41404 KB |
Output is correct |
18 |
Correct |
19 ms |
41400 KB |
Output is correct |
19 |
Correct |
28 ms |
41292 KB |
Output is correct |
20 |
Correct |
23 ms |
41328 KB |
Output is correct |
21 |
Correct |
26 ms |
41336 KB |
Output is correct |
22 |
Correct |
22 ms |
41356 KB |
Output is correct |
23 |
Correct |
21 ms |
41380 KB |
Output is correct |
24 |
Correct |
21 ms |
41420 KB |
Output is correct |
25 |
Correct |
20 ms |
41388 KB |
Output is correct |
26 |
Correct |
20 ms |
41380 KB |
Output is correct |
27 |
Correct |
25 ms |
41668 KB |
Output is correct |
28 |
Correct |
23 ms |
41804 KB |
Output is correct |
29 |
Correct |
22 ms |
41672 KB |
Output is correct |
30 |
Correct |
22 ms |
41524 KB |
Output is correct |
31 |
Correct |
21 ms |
41504 KB |
Output is correct |
32 |
Correct |
20 ms |
41420 KB |
Output is correct |
33 |
Correct |
22 ms |
41532 KB |
Output is correct |
34 |
Correct |
22 ms |
41452 KB |
Output is correct |
35 |
Correct |
22 ms |
41540 KB |
Output is correct |
36 |
Correct |
21 ms |
41692 KB |
Output is correct |
37 |
Correct |
22 ms |
41676 KB |
Output is correct |
38 |
Correct |
22 ms |
41656 KB |
Output is correct |
39 |
Correct |
24 ms |
41772 KB |
Output is correct |
40 |
Correct |
22 ms |
41520 KB |
Output is correct |
41 |
Correct |
23 ms |
41676 KB |
Output is correct |
42 |
Correct |
459 ms |
81720 KB |
Output is correct |
43 |
Correct |
727 ms |
102704 KB |
Output is correct |
44 |
Correct |
102 ms |
51136 KB |
Output is correct |
45 |
Correct |
588 ms |
88708 KB |
Output is correct |
46 |
Correct |
231 ms |
87084 KB |
Output is correct |
47 |
Correct |
22 ms |
41336 KB |
Output is correct |
48 |
Correct |
20 ms |
41296 KB |
Output is correct |
49 |
Correct |
21 ms |
41296 KB |
Output is correct |
50 |
Correct |
226 ms |
83936 KB |
Output is correct |
51 |
Correct |
228 ms |
87144 KB |
Output is correct |
52 |
Correct |
307 ms |
81620 KB |
Output is correct |
53 |
Correct |
300 ms |
81556 KB |
Output is correct |
54 |
Correct |
333 ms |
81576 KB |
Output is correct |
55 |
Correct |
472 ms |
88092 KB |
Output is correct |
56 |
Correct |
366 ms |
95544 KB |
Output is correct |
57 |
Correct |
334 ms |
92348 KB |
Output is correct |
58 |
Correct |
624 ms |
100748 KB |
Output is correct |
59 |
Correct |
1173 ms |
95196 KB |
Output is correct |
60 |
Correct |
465 ms |
94100 KB |
Output is correct |
61 |
Correct |
480 ms |
93748 KB |
Output is correct |
62 |
Correct |
479 ms |
90120 KB |
Output is correct |
63 |
Correct |
358 ms |
92300 KB |
Output is correct |
64 |
Correct |
25 ms |
42056 KB |
Output is correct |
65 |
Correct |
24 ms |
42184 KB |
Output is correct |
66 |
Correct |
556 ms |
90040 KB |
Output is correct |
67 |
Correct |
44 ms |
45892 KB |
Output is correct |
68 |
Correct |
60 ms |
48936 KB |
Output is correct |
69 |
Correct |
1179 ms |
95288 KB |
Output is correct |
70 |
Correct |
97 ms |
56640 KB |
Output is correct |
71 |
Correct |
267 ms |
88044 KB |
Output is correct |
72 |
Correct |
1150 ms |
95292 KB |
Output is correct |
73 |
Correct |
540 ms |
90076 KB |
Output is correct |