# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
615600 |
2022-07-31T11:00:52 Z |
SeDunion |
Keys (IOI21_keys) |
C++17 |
|
1175 ms |
120244 KB |
#include "keys.h"
#include <iostream>
#include <vector>
#include <set>
using namespace std;
using vi = vector<int>;
const int N = 300'005;
set<int>keys[N];
set<pair<int,int>>maybe[N];
vector<int>ac[N];
int tree[N];
int gtree(int x) { if (x == tree[x]) return x; return tree[x] = gtree(tree[x]); }
int cc[N];
int gcc(int x) { if (x == cc[x]) return x; return cc[x] = gcc(cc[x]); }
int par[N];
void add_edge(int x, int y) { tree[x] = par[x] = y; }
vector<pair<int,int>>del;
void unite(int x, int y) {
x = gcc(x), y = gcc(y);
if (x == y) return;
if (keys[x].size() + maybe[x].size() + ac[x].size() >
keys[y].size() + maybe[y].size() + ac[y].size()) swap(x, y);
cc[x] = y;
for (auto u : ac[x]) ac[y].emplace_back(u);
ac[x].clear();
for (auto u : keys[x]) {
if (keys[y].count(u)) continue;
auto it = maybe[y].lower_bound({u, -1});
while (it != maybe[y].end() && it->first == u) {
del.emplace_back(*it);
ac[y].emplace_back(it->second);
++it;
}
keys[y].insert(u);
}
for (auto i : del) maybe[y].erase(i); del.clear();
keys[x].clear();
for (auto it : maybe[x]) {
if (keys[y].count(it.first)) ac[y].emplace_back(it.second);
else maybe[y].insert(it);
}
maybe[x].clear();
}
void collapse(int x, int y) {
while (x != y) {
unite(x, y);
y = par[y];
}
int a = gtree(gcc(x)), b = gcc(x);
tree[b] = tree[a] = b;
}
void push(int v) {
v = gtree(gcc(v));
while (ac[v].size()) {
int t = ac[v].back(); ac[v].pop_back();
t = gcc(t);
if (v == t) continue;
int tv = gtree(v);
int tt = gtree(t);
if (tv != tt) {
add_edge(v, tt);
push(t);
return;
}
// cycle
collapse(v, t);
push(v);
return;
}
}
vi norm(int n, vi a) {
vi r(n);
for (int i : a) r[i] = 1;
return r;
}
vi find_reachable(vi r, vi u, vi v, vi c) {
int n = r.size();
int m = u.size();
vi ans;
for (int i = 0 ; i < n ; ++ i) {
tree[i] = cc[i] = par[i] = i;
}
for (int i = 0 ; i < m ; ++ i) {
maybe[u[i]].insert({c[i], v[i]});
maybe[v[i]].insert({c[i], u[i]});
}
for (int i = 0 ; i < n ; ++ i) {
keys[i].insert(r[i]);
auto it = maybe[i].lower_bound({r[i], -1});
while (it != maybe[i].end() && it->first == r[i]) ac[i].emplace_back(it->second), it++;
if (ac[i].empty()) ans.emplace_back(i);
}
if (ans.size()) return norm(n, ans);
for (int i = 0 ; i < n ; ++ i) {
push(i);
}
vi cnt(n);
for (int i = 0 ; i < n ; ++ i) {
int x = gcc(i);
if (x == gtree(x)) cnt[x]++;
else cnt[x] = N;
}
int mn = N;
for (int i = 0 ; i < n ; ++ i) {
int x = gcc(i);
mn = min(mn, cnt[x]);
}
for (int i = 0 ; i < n ; ++ i) {
int x = gcc(i);
if (cnt[x] == mn) ans.emplace_back(i);
}
return norm(n, ans);
}
Compilation message
keys.cpp: In function 'void unite(int, int)':
keys.cpp:45:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
45 | for (auto i : del) maybe[y].erase(i); del.clear();
| ^~~
keys.cpp:45:40: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
45 | for (auto i : del) maybe[y].erase(i); del.clear();
| ^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
17 ms |
35540 KB |
Output is correct |
2 |
Correct |
19 ms |
35540 KB |
Output is correct |
3 |
Correct |
16 ms |
35444 KB |
Output is correct |
4 |
Correct |
19 ms |
35500 KB |
Output is correct |
5 |
Correct |
17 ms |
35528 KB |
Output is correct |
6 |
Correct |
16 ms |
35540 KB |
Output is correct |
7 |
Correct |
18 ms |
35540 KB |
Output is correct |
8 |
Correct |
17 ms |
35540 KB |
Output is correct |
9 |
Correct |
17 ms |
35516 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
17 ms |
35540 KB |
Output is correct |
2 |
Correct |
19 ms |
35540 KB |
Output is correct |
3 |
Correct |
16 ms |
35444 KB |
Output is correct |
4 |
Correct |
19 ms |
35500 KB |
Output is correct |
5 |
Correct |
17 ms |
35528 KB |
Output is correct |
6 |
Correct |
16 ms |
35540 KB |
Output is correct |
7 |
Correct |
18 ms |
35540 KB |
Output is correct |
8 |
Correct |
17 ms |
35540 KB |
Output is correct |
9 |
Correct |
17 ms |
35516 KB |
Output is correct |
10 |
Correct |
16 ms |
35540 KB |
Output is correct |
11 |
Correct |
19 ms |
35520 KB |
Output is correct |
12 |
Correct |
17 ms |
35536 KB |
Output is correct |
13 |
Correct |
16 ms |
35476 KB |
Output is correct |
14 |
Correct |
17 ms |
35540 KB |
Output is correct |
15 |
Correct |
17 ms |
35540 KB |
Output is correct |
16 |
Correct |
16 ms |
35548 KB |
Output is correct |
17 |
Correct |
17 ms |
35540 KB |
Output is correct |
18 |
Correct |
18 ms |
35444 KB |
Output is correct |
19 |
Correct |
19 ms |
35548 KB |
Output is correct |
20 |
Correct |
18 ms |
35540 KB |
Output is correct |
21 |
Correct |
18 ms |
35540 KB |
Output is correct |
22 |
Correct |
17 ms |
35560 KB |
Output is correct |
23 |
Correct |
17 ms |
35516 KB |
Output is correct |
24 |
Correct |
16 ms |
35540 KB |
Output is correct |
25 |
Correct |
21 ms |
35536 KB |
Output is correct |
26 |
Correct |
17 ms |
35580 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
17 ms |
35540 KB |
Output is correct |
2 |
Correct |
19 ms |
35540 KB |
Output is correct |
3 |
Correct |
16 ms |
35444 KB |
Output is correct |
4 |
Correct |
19 ms |
35500 KB |
Output is correct |
5 |
Correct |
17 ms |
35528 KB |
Output is correct |
6 |
Correct |
16 ms |
35540 KB |
Output is correct |
7 |
Correct |
18 ms |
35540 KB |
Output is correct |
8 |
Correct |
17 ms |
35540 KB |
Output is correct |
9 |
Correct |
17 ms |
35516 KB |
Output is correct |
10 |
Correct |
16 ms |
35540 KB |
Output is correct |
11 |
Correct |
19 ms |
35520 KB |
Output is correct |
12 |
Correct |
17 ms |
35536 KB |
Output is correct |
13 |
Correct |
16 ms |
35476 KB |
Output is correct |
14 |
Correct |
17 ms |
35540 KB |
Output is correct |
15 |
Correct |
17 ms |
35540 KB |
Output is correct |
16 |
Correct |
16 ms |
35548 KB |
Output is correct |
17 |
Correct |
17 ms |
35540 KB |
Output is correct |
18 |
Correct |
18 ms |
35444 KB |
Output is correct |
19 |
Correct |
19 ms |
35548 KB |
Output is correct |
20 |
Correct |
18 ms |
35540 KB |
Output is correct |
21 |
Correct |
18 ms |
35540 KB |
Output is correct |
22 |
Correct |
17 ms |
35560 KB |
Output is correct |
23 |
Correct |
17 ms |
35516 KB |
Output is correct |
24 |
Correct |
16 ms |
35540 KB |
Output is correct |
25 |
Correct |
21 ms |
35536 KB |
Output is correct |
26 |
Correct |
17 ms |
35580 KB |
Output is correct |
27 |
Correct |
18 ms |
35868 KB |
Output is correct |
28 |
Correct |
18 ms |
35924 KB |
Output is correct |
29 |
Correct |
21 ms |
35908 KB |
Output is correct |
30 |
Correct |
18 ms |
35752 KB |
Output is correct |
31 |
Correct |
19 ms |
35644 KB |
Output is correct |
32 |
Correct |
17 ms |
35616 KB |
Output is correct |
33 |
Correct |
17 ms |
35652 KB |
Output is correct |
34 |
Correct |
19 ms |
35732 KB |
Output is correct |
35 |
Correct |
17 ms |
35668 KB |
Output is correct |
36 |
Correct |
17 ms |
35796 KB |
Output is correct |
37 |
Correct |
20 ms |
35796 KB |
Output is correct |
38 |
Correct |
25 ms |
35868 KB |
Output is correct |
39 |
Correct |
20 ms |
35900 KB |
Output is correct |
40 |
Correct |
18 ms |
35740 KB |
Output is correct |
41 |
Correct |
19 ms |
35832 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
17 ms |
35540 KB |
Output is correct |
2 |
Correct |
19 ms |
35540 KB |
Output is correct |
3 |
Correct |
16 ms |
35444 KB |
Output is correct |
4 |
Correct |
19 ms |
35500 KB |
Output is correct |
5 |
Correct |
17 ms |
35528 KB |
Output is correct |
6 |
Correct |
16 ms |
35540 KB |
Output is correct |
7 |
Correct |
18 ms |
35540 KB |
Output is correct |
8 |
Correct |
17 ms |
35540 KB |
Output is correct |
9 |
Correct |
17 ms |
35516 KB |
Output is correct |
10 |
Correct |
362 ms |
80332 KB |
Output is correct |
11 |
Correct |
671 ms |
108220 KB |
Output is correct |
12 |
Correct |
94 ms |
48076 KB |
Output is correct |
13 |
Correct |
469 ms |
99088 KB |
Output is correct |
14 |
Correct |
241 ms |
114264 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
17 ms |
35540 KB |
Output is correct |
2 |
Correct |
19 ms |
35540 KB |
Output is correct |
3 |
Correct |
16 ms |
35444 KB |
Output is correct |
4 |
Correct |
19 ms |
35500 KB |
Output is correct |
5 |
Correct |
17 ms |
35528 KB |
Output is correct |
6 |
Correct |
16 ms |
35540 KB |
Output is correct |
7 |
Correct |
18 ms |
35540 KB |
Output is correct |
8 |
Correct |
17 ms |
35540 KB |
Output is correct |
9 |
Correct |
17 ms |
35516 KB |
Output is correct |
10 |
Correct |
16 ms |
35540 KB |
Output is correct |
11 |
Correct |
19 ms |
35520 KB |
Output is correct |
12 |
Correct |
17 ms |
35536 KB |
Output is correct |
13 |
Correct |
16 ms |
35476 KB |
Output is correct |
14 |
Correct |
17 ms |
35540 KB |
Output is correct |
15 |
Correct |
17 ms |
35540 KB |
Output is correct |
16 |
Correct |
16 ms |
35548 KB |
Output is correct |
17 |
Correct |
17 ms |
35540 KB |
Output is correct |
18 |
Correct |
18 ms |
35444 KB |
Output is correct |
19 |
Correct |
19 ms |
35548 KB |
Output is correct |
20 |
Correct |
18 ms |
35540 KB |
Output is correct |
21 |
Correct |
18 ms |
35540 KB |
Output is correct |
22 |
Correct |
17 ms |
35560 KB |
Output is correct |
23 |
Correct |
17 ms |
35516 KB |
Output is correct |
24 |
Correct |
16 ms |
35540 KB |
Output is correct |
25 |
Correct |
21 ms |
35536 KB |
Output is correct |
26 |
Correct |
17 ms |
35580 KB |
Output is correct |
27 |
Correct |
18 ms |
35868 KB |
Output is correct |
28 |
Correct |
18 ms |
35924 KB |
Output is correct |
29 |
Correct |
21 ms |
35908 KB |
Output is correct |
30 |
Correct |
18 ms |
35752 KB |
Output is correct |
31 |
Correct |
19 ms |
35644 KB |
Output is correct |
32 |
Correct |
17 ms |
35616 KB |
Output is correct |
33 |
Correct |
17 ms |
35652 KB |
Output is correct |
34 |
Correct |
19 ms |
35732 KB |
Output is correct |
35 |
Correct |
17 ms |
35668 KB |
Output is correct |
36 |
Correct |
17 ms |
35796 KB |
Output is correct |
37 |
Correct |
20 ms |
35796 KB |
Output is correct |
38 |
Correct |
25 ms |
35868 KB |
Output is correct |
39 |
Correct |
20 ms |
35900 KB |
Output is correct |
40 |
Correct |
18 ms |
35740 KB |
Output is correct |
41 |
Correct |
19 ms |
35832 KB |
Output is correct |
42 |
Correct |
362 ms |
80332 KB |
Output is correct |
43 |
Correct |
671 ms |
108220 KB |
Output is correct |
44 |
Correct |
94 ms |
48076 KB |
Output is correct |
45 |
Correct |
469 ms |
99088 KB |
Output is correct |
46 |
Correct |
241 ms |
114264 KB |
Output is correct |
47 |
Correct |
16 ms |
35480 KB |
Output is correct |
48 |
Correct |
21 ms |
35492 KB |
Output is correct |
49 |
Correct |
20 ms |
35428 KB |
Output is correct |
50 |
Correct |
257 ms |
105420 KB |
Output is correct |
51 |
Correct |
228 ms |
109088 KB |
Output is correct |
52 |
Correct |
272 ms |
81988 KB |
Output is correct |
53 |
Correct |
261 ms |
82000 KB |
Output is correct |
54 |
Correct |
264 ms |
82028 KB |
Output is correct |
55 |
Correct |
413 ms |
85716 KB |
Output is correct |
56 |
Correct |
443 ms |
105596 KB |
Output is correct |
57 |
Correct |
556 ms |
103392 KB |
Output is correct |
58 |
Correct |
468 ms |
109068 KB |
Output is correct |
59 |
Correct |
1103 ms |
102668 KB |
Output is correct |
60 |
Correct |
389 ms |
97700 KB |
Output is correct |
61 |
Correct |
438 ms |
98064 KB |
Output is correct |
62 |
Correct |
399 ms |
90360 KB |
Output is correct |
63 |
Correct |
246 ms |
96492 KB |
Output is correct |
64 |
Correct |
20 ms |
36676 KB |
Output is correct |
65 |
Correct |
20 ms |
36692 KB |
Output is correct |
66 |
Correct |
383 ms |
90276 KB |
Output is correct |
67 |
Correct |
39 ms |
43216 KB |
Output is correct |
68 |
Correct |
53 ms |
48832 KB |
Output is correct |
69 |
Correct |
1136 ms |
102356 KB |
Output is correct |
70 |
Correct |
99 ms |
62264 KB |
Output is correct |
71 |
Correct |
263 ms |
120244 KB |
Output is correct |
72 |
Correct |
1175 ms |
102544 KB |
Output is correct |
73 |
Correct |
391 ms |
90268 KB |
Output is correct |