# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
824030 |
2023-08-13T11:41:42 Z |
PixelCat |
Keys (IOI21_keys) |
C++17 |
|
950 ms |
142484 KB |
#ifdef NYAOWO
#include "grader.cpp"
#endif
#include <bits/stdc++.h>
#define For(i, a, b) for(int i = a; i <= b; i++)
#define Forr(i, a, b) for(int i = a; i >= b; i--)
#define F first
#define S second
#define sz(x) ((int)x.size())
#define all(x) x.begin(), x.end()
#define eb emplace_back
// #define int LL
using namespace std;
using i32 = int32_t;
using LL = long long;
using pii = pair<int, int>;
const int MAXN = 300'000;
struct DSU {
int p[MAXN + 10];
int sz[MAXN + 10];
void init() {
memset(p, -1, sizeof(p));
memset(sz, 0, sizeof(sz));
}
int find(int n) {
if(p[n] < 0) return n;
return p[n] = find(p[n]);
}
void uni(int a, int b) {
a = find(a); b = find(b);
if(a == b) return;
p[b] = a;
sz[a] += sz[b] + 1;
}
bool same(int a, int b) {
return find(a) == find(b);
}
int size(int n) {
return sz[find(n)] + 1;
}
} dsu, big_dsu;
set<int> keys[MAXN + 10];
vector<int> edges[MAXN * 2 + 10];
unordered_map<int, int> locked[MAXN + 10]; // key -> vertices
vector<int> unlocked[MAXN + 10];
int ayaya[MAXN + 10];
// merge v2 into v1
void merge_vector(vector<int> &v1, vector<int> &v2) {
if(sz(v1) < sz(v2)) v1.swap(v2);
v1.insert(v1.end(), all(v2));
v2.clear();
}
int merge_groups(int a, int b) {
assert(dsu.find(a) == a && dsu.find(b) == b && a != b);
// if(sz(keys[a]) + sz(locked[a]) < sz(keys[b]) + sz(locked[b])) swap(a, b);
if(sz(keys[a]) + sz(locked[a]) < sz(keys[b]) + sz(locked[b])) {
keys[a].swap(keys[b]);
locked[a].swap(locked[b]);
}
// merge b into a
// merge keys
for(auto &k:keys[b]) if(!keys[a].count(k)) {
if(locked[a].count(k)) {
merge_vector(unlocked[a], edges[locked[a][k]]);
locked[a].erase(k);
}
keys[a].insert(k);
}
keys[b].clear();
// merge locked edges
for(auto &it:locked[b]) {
if(keys[a].count(it.F)) {
merge_vector(unlocked[a], edges[it.S]);
} else if(locked[a].count(it.F)) {
merge_vector(edges[locked[a][it.F]], edges[it.S]);
} else {
locked[a][it.F] = it.S;
}
}
locked[b].clear();
// merge unlocked edges
merge_vector(unlocked[a], unlocked[b]);
dsu.uni(a, b);
return a;
}
vector<i32> find_reachable(vector<i32> R, vector<i32> U, vector<i32> V, vector<i32> C) {
int n = sz(R);
int m = sz(C);
For(i, 0, n - 1) {
keys[i].insert(R[i]);
}
int ptr = 0;
For(i, 0, m - 1) {
int a = U[i], b = V[i], c = C[i];
if(R[a] == c) {
unlocked[a].eb(b);
} else {
if(!locked[a].count(c)) locked[a][c] = (ptr++);
edges[locked[a][c]].eb(b);
}
if(R[b] == c) {
unlocked[b].eb(a);
} else {
if(!locked[b].count(c)) locked[b][c] = (ptr++);
edges[locked[b][c]].eb(a);
}
}
dsu.init();
big_dsu.init();
memset(ayaya, -1, sizeof(ayaya));
For(start, 0, n - 1) {
int cur = start;
while(sz(unlocked[cur])) {
int nxt = unlocked[cur].back();
unlocked[cur].pop_back();
nxt = dsu.find(nxt);
if(cur == nxt) {
;
} else if(!big_dsu.same(cur, nxt)) {
ayaya[cur] = nxt;
big_dsu.uni(cur, nxt);
break;
} else {
vector<int> sus;
while(nxt != cur) {
sus.eb(nxt);
nxt = dsu.find(ayaya[nxt]);
}
for(auto &i:sus) {
cur = merge_groups(cur, i);
}
ayaya[cur] = -1;
}
}
}
int mn = n * 8;
For(i, 0, n - 1) if(dsu.find(i) == i && ayaya[i] == -1) {
mn = min(mn, dsu.size(i));
}
// cerr << mn << "\n";
// For(i, 0, n - 1) cerr << dsu.find(i) << " \n"[i == n - 1];
// For(i, 0, n - 1) cerr << ayaya[i] << " \n"[i == n - 1];
vector<int> ret(n);
For(i, 0, n - 1) {
int owo = dsu.find(i);
if(ayaya[owo] == -1 && dsu.size(owo) == mn) {
ret[i] = 1;
} else {
ret[i] = 0;
}
}
return ret;
}
/*
4 5
0 1 1 2
0 1 0
0 2 0
1 2 1
1 3 0
3 1 2
0 1 1 0
7 10
0 1 1 2 2 1 2
0 1 0
0 2 0
1 2 1
1 3 0
2 3 0
3 4 1
3 5 2
4 5 0
4 6 2
5 6 1
0 1 1 0 1 0 1
3 1
0 0 0
0 1 0
0 0 1
*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
24 ms |
57764 KB |
Output is correct |
2 |
Correct |
25 ms |
57780 KB |
Output is correct |
3 |
Correct |
25 ms |
57800 KB |
Output is correct |
4 |
Correct |
25 ms |
57832 KB |
Output is correct |
5 |
Correct |
27 ms |
57812 KB |
Output is correct |
6 |
Correct |
26 ms |
57832 KB |
Output is correct |
7 |
Correct |
26 ms |
57812 KB |
Output is correct |
8 |
Correct |
26 ms |
57812 KB |
Output is correct |
9 |
Correct |
25 ms |
57852 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
24 ms |
57764 KB |
Output is correct |
2 |
Correct |
25 ms |
57780 KB |
Output is correct |
3 |
Correct |
25 ms |
57800 KB |
Output is correct |
4 |
Correct |
25 ms |
57832 KB |
Output is correct |
5 |
Correct |
27 ms |
57812 KB |
Output is correct |
6 |
Correct |
26 ms |
57832 KB |
Output is correct |
7 |
Correct |
26 ms |
57812 KB |
Output is correct |
8 |
Correct |
26 ms |
57812 KB |
Output is correct |
9 |
Correct |
25 ms |
57852 KB |
Output is correct |
10 |
Correct |
25 ms |
57812 KB |
Output is correct |
11 |
Correct |
24 ms |
57816 KB |
Output is correct |
12 |
Correct |
25 ms |
57864 KB |
Output is correct |
13 |
Correct |
25 ms |
57812 KB |
Output is correct |
14 |
Correct |
26 ms |
57736 KB |
Output is correct |
15 |
Correct |
27 ms |
57804 KB |
Output is correct |
16 |
Correct |
26 ms |
57768 KB |
Output is correct |
17 |
Correct |
29 ms |
57816 KB |
Output is correct |
18 |
Correct |
26 ms |
57860 KB |
Output is correct |
19 |
Correct |
25 ms |
57784 KB |
Output is correct |
20 |
Correct |
25 ms |
57812 KB |
Output is correct |
21 |
Correct |
26 ms |
57840 KB |
Output is correct |
22 |
Correct |
26 ms |
57852 KB |
Output is correct |
23 |
Correct |
25 ms |
57812 KB |
Output is correct |
24 |
Correct |
26 ms |
57812 KB |
Output is correct |
25 |
Correct |
26 ms |
57808 KB |
Output is correct |
26 |
Correct |
25 ms |
57768 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
24 ms |
57764 KB |
Output is correct |
2 |
Correct |
25 ms |
57780 KB |
Output is correct |
3 |
Correct |
25 ms |
57800 KB |
Output is correct |
4 |
Correct |
25 ms |
57832 KB |
Output is correct |
5 |
Correct |
27 ms |
57812 KB |
Output is correct |
6 |
Correct |
26 ms |
57832 KB |
Output is correct |
7 |
Correct |
26 ms |
57812 KB |
Output is correct |
8 |
Correct |
26 ms |
57812 KB |
Output is correct |
9 |
Correct |
25 ms |
57852 KB |
Output is correct |
10 |
Correct |
25 ms |
57812 KB |
Output is correct |
11 |
Correct |
24 ms |
57816 KB |
Output is correct |
12 |
Correct |
25 ms |
57864 KB |
Output is correct |
13 |
Correct |
25 ms |
57812 KB |
Output is correct |
14 |
Correct |
26 ms |
57736 KB |
Output is correct |
15 |
Correct |
27 ms |
57804 KB |
Output is correct |
16 |
Correct |
26 ms |
57768 KB |
Output is correct |
17 |
Correct |
29 ms |
57816 KB |
Output is correct |
18 |
Correct |
26 ms |
57860 KB |
Output is correct |
19 |
Correct |
25 ms |
57784 KB |
Output is correct |
20 |
Correct |
25 ms |
57812 KB |
Output is correct |
21 |
Correct |
26 ms |
57840 KB |
Output is correct |
22 |
Correct |
26 ms |
57852 KB |
Output is correct |
23 |
Correct |
25 ms |
57812 KB |
Output is correct |
24 |
Correct |
26 ms |
57812 KB |
Output is correct |
25 |
Correct |
26 ms |
57808 KB |
Output is correct |
26 |
Correct |
25 ms |
57768 KB |
Output is correct |
27 |
Correct |
28 ms |
58324 KB |
Output is correct |
28 |
Correct |
32 ms |
58400 KB |
Output is correct |
29 |
Correct |
28 ms |
58412 KB |
Output is correct |
30 |
Correct |
27 ms |
58028 KB |
Output is correct |
31 |
Correct |
26 ms |
58020 KB |
Output is correct |
32 |
Correct |
27 ms |
57900 KB |
Output is correct |
33 |
Correct |
27 ms |
58084 KB |
Output is correct |
34 |
Correct |
27 ms |
57992 KB |
Output is correct |
35 |
Correct |
29 ms |
58080 KB |
Output is correct |
36 |
Correct |
27 ms |
58316 KB |
Output is correct |
37 |
Correct |
26 ms |
58288 KB |
Output is correct |
38 |
Correct |
28 ms |
58284 KB |
Output is correct |
39 |
Correct |
27 ms |
58380 KB |
Output is correct |
40 |
Correct |
26 ms |
58132 KB |
Output is correct |
41 |
Correct |
27 ms |
58236 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
24 ms |
57764 KB |
Output is correct |
2 |
Correct |
25 ms |
57780 KB |
Output is correct |
3 |
Correct |
25 ms |
57800 KB |
Output is correct |
4 |
Correct |
25 ms |
57832 KB |
Output is correct |
5 |
Correct |
27 ms |
57812 KB |
Output is correct |
6 |
Correct |
26 ms |
57832 KB |
Output is correct |
7 |
Correct |
26 ms |
57812 KB |
Output is correct |
8 |
Correct |
26 ms |
57812 KB |
Output is correct |
9 |
Correct |
25 ms |
57852 KB |
Output is correct |
10 |
Correct |
546 ms |
110200 KB |
Output is correct |
11 |
Correct |
288 ms |
97040 KB |
Output is correct |
12 |
Correct |
92 ms |
73284 KB |
Output is correct |
13 |
Correct |
515 ms |
137832 KB |
Output is correct |
14 |
Correct |
163 ms |
97508 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
24 ms |
57764 KB |
Output is correct |
2 |
Correct |
25 ms |
57780 KB |
Output is correct |
3 |
Correct |
25 ms |
57800 KB |
Output is correct |
4 |
Correct |
25 ms |
57832 KB |
Output is correct |
5 |
Correct |
27 ms |
57812 KB |
Output is correct |
6 |
Correct |
26 ms |
57832 KB |
Output is correct |
7 |
Correct |
26 ms |
57812 KB |
Output is correct |
8 |
Correct |
26 ms |
57812 KB |
Output is correct |
9 |
Correct |
25 ms |
57852 KB |
Output is correct |
10 |
Correct |
25 ms |
57812 KB |
Output is correct |
11 |
Correct |
24 ms |
57816 KB |
Output is correct |
12 |
Correct |
25 ms |
57864 KB |
Output is correct |
13 |
Correct |
25 ms |
57812 KB |
Output is correct |
14 |
Correct |
26 ms |
57736 KB |
Output is correct |
15 |
Correct |
27 ms |
57804 KB |
Output is correct |
16 |
Correct |
26 ms |
57768 KB |
Output is correct |
17 |
Correct |
29 ms |
57816 KB |
Output is correct |
18 |
Correct |
26 ms |
57860 KB |
Output is correct |
19 |
Correct |
25 ms |
57784 KB |
Output is correct |
20 |
Correct |
25 ms |
57812 KB |
Output is correct |
21 |
Correct |
26 ms |
57840 KB |
Output is correct |
22 |
Correct |
26 ms |
57852 KB |
Output is correct |
23 |
Correct |
25 ms |
57812 KB |
Output is correct |
24 |
Correct |
26 ms |
57812 KB |
Output is correct |
25 |
Correct |
26 ms |
57808 KB |
Output is correct |
26 |
Correct |
25 ms |
57768 KB |
Output is correct |
27 |
Correct |
28 ms |
58324 KB |
Output is correct |
28 |
Correct |
32 ms |
58400 KB |
Output is correct |
29 |
Correct |
28 ms |
58412 KB |
Output is correct |
30 |
Correct |
27 ms |
58028 KB |
Output is correct |
31 |
Correct |
26 ms |
58020 KB |
Output is correct |
32 |
Correct |
27 ms |
57900 KB |
Output is correct |
33 |
Correct |
27 ms |
58084 KB |
Output is correct |
34 |
Correct |
27 ms |
57992 KB |
Output is correct |
35 |
Correct |
29 ms |
58080 KB |
Output is correct |
36 |
Correct |
27 ms |
58316 KB |
Output is correct |
37 |
Correct |
26 ms |
58288 KB |
Output is correct |
38 |
Correct |
28 ms |
58284 KB |
Output is correct |
39 |
Correct |
27 ms |
58380 KB |
Output is correct |
40 |
Correct |
26 ms |
58132 KB |
Output is correct |
41 |
Correct |
27 ms |
58236 KB |
Output is correct |
42 |
Correct |
546 ms |
110200 KB |
Output is correct |
43 |
Correct |
288 ms |
97040 KB |
Output is correct |
44 |
Correct |
92 ms |
73284 KB |
Output is correct |
45 |
Correct |
515 ms |
137832 KB |
Output is correct |
46 |
Correct |
163 ms |
97508 KB |
Output is correct |
47 |
Correct |
27 ms |
57780 KB |
Output is correct |
48 |
Correct |
27 ms |
57740 KB |
Output is correct |
49 |
Correct |
25 ms |
57708 KB |
Output is correct |
50 |
Correct |
158 ms |
94208 KB |
Output is correct |
51 |
Correct |
184 ms |
94436 KB |
Output is correct |
52 |
Correct |
263 ms |
121108 KB |
Output is correct |
53 |
Correct |
257 ms |
121064 KB |
Output is correct |
54 |
Correct |
273 ms |
121072 KB |
Output is correct |
55 |
Correct |
564 ms |
117756 KB |
Output is correct |
56 |
Correct |
329 ms |
142484 KB |
Output is correct |
57 |
Correct |
269 ms |
139216 KB |
Output is correct |
58 |
Correct |
279 ms |
117268 KB |
Output is correct |
59 |
Correct |
796 ms |
124548 KB |
Output is correct |
60 |
Correct |
413 ms |
128280 KB |
Output is correct |
61 |
Correct |
700 ms |
130812 KB |
Output is correct |
62 |
Correct |
949 ms |
120332 KB |
Output is correct |
63 |
Correct |
285 ms |
122992 KB |
Output is correct |
64 |
Correct |
30 ms |
58436 KB |
Output is correct |
65 |
Correct |
28 ms |
58572 KB |
Output is correct |
66 |
Correct |
936 ms |
120364 KB |
Output is correct |
67 |
Correct |
42 ms |
62028 KB |
Output is correct |
68 |
Correct |
49 ms |
64776 KB |
Output is correct |
69 |
Correct |
792 ms |
124484 KB |
Output is correct |
70 |
Correct |
71 ms |
71812 KB |
Output is correct |
71 |
Correct |
172 ms |
97788 KB |
Output is correct |
72 |
Correct |
745 ms |
124488 KB |
Output is correct |
73 |
Correct |
950 ms |
120292 KB |
Output is correct |