# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
448741 |
2021-08-01T09:12:57 Z |
grt |
Keys (IOI21_keys) |
C++17 |
|
1585 ms |
184236 KB |
#include <bits/stdc++.h>
#define ST first
#define ND second
#define PB push_back
using namespace std;
using ll = long long;
using pi = pair<int,int>;
using vi = vector<int>;
const int nax = 300 * 1000 + 10;
int n, m;
vector<pi>V[nax];
int par[nax];
set<int>reach[nax];
int p[nax], deg[nax];
vi vertices[nax];
bool done[nax];
map<int, vi> graph[nax];
vi edges[nax];
int G[nax];
int p2[nax], siz[nax];
int Fund(int x) {
if(p2[x] != x) p2[x] = Fund(p2[x]);
return p2[x];
}
bool Onion(int a, int b) {
a = Fund(a); b = Fund(b);
if(a == b) return false;
if(siz[a] < siz[b]) swap(a, b);
p2[b] = a;
siz[a] += siz[b];
return true;
}
void merge(int a, int b) {
if(p[a] == p[b]) return;
if((int)vertices[p[a]].size() < (int)vertices[p[b]].size()) swap(a, b);
int pb = p[b];
if(G[p[a]] < G[pb]) {
swap(G[p[a]], G[pb]);
reach[p[a]].swap(reach[pb]);
graph[pb].swap(graph[p[a]]);
}
for(auto &it : graph[pb]) {
if(reach[p[a]].count(it.ST)) {
for(int &x : it.ND) {
edges[p[a]].PB(x);
}
} else {
for(int &x : it.ND) {
graph[p[a]][it.ST].PB(x);
}
}
}
G[p[a]] += G[pb];
graph[pb].clear();
for(int x : vertices[pb]) {
p[x] = p[a];
vertices[p[a]].PB(x);
}
for(int x : reach[pb]) {
if(!reach[p[a]].count(x)) {
for(int &y : graph[p[a]][x]) {
edges[p[a]].PB(y);
}
graph[p[a]][x].clear();
}
reach[p[a]].insert(x);
}
if((int)edges[p[a]].size() < (int)edges[pb].size()) edges[p[a]].swap(edges[pb]);
for(int x : edges[pb]) {
edges[p[a]].PB(x);
}
edges[pb].clear();
vertices[pb].clear();
reach[pb].clear();
}
vi find_reachable(vi r, vi u, vi v, vi c) {
n = (int)r.size();
m = (int)u.size();
for(int i = 0; i < m; ++i) {
V[u[i]].emplace_back(v[i], c[i]);
V[v[i]].emplace_back(u[i], c[i]);
}
vi tmp = {};
for(int i = 0; i < n; ++i) {
p2[i] = i; siz[i] = 1;
}
for(int i = 0; i < n; ++i) {
bool any = false;
for(auto nbh : V[i]) {
if(r[i] == nbh.ND) {
par[i] = nbh.ST;
edges[i].PB(nbh.ST);
any = true;
}
graph[i][nbh.ND].PB(nbh.ST);
}
G[i] = (int)V[i].size();
if(!any) {
tmp.PB(i);
}
reach[i].insert(r[i]);
vertices[i].PB(i);
p[i] = i;
deg[par[i]]++;
Onion(par[i], i);
}
if((int)tmp.size() > 0) {
vi ans(n);
for(int x : tmp) ans[x] = true;
return ans;
}
vi zeroDeg = {};
for(int i = 0; i < n; ++i) {
if(deg[i] == 0) {
zeroDeg.PB(i);
}
}
while((int)zeroDeg.size() > 0) {
int x = zeroDeg.back();
done[x] = true;
zeroDeg.pop_back();
deg[par[x]]--;
if(deg[par[x]] == 0) zeroDeg.PB(par[x]);
}
vi roots;
for(int i = 0; i < n; ++i) {
if(!done[i]) {
vi cycle = {i};
int x = i;
done[i] = true;
while(par[x] != i) {
x = par[x];
done[x] = true;
cycle.PB(x);
}
for(int j = 1; j < (int)cycle.size(); ++j) {
merge(cycle[j - 1], cycle[j]);
}
roots.PB(p[i]);
}
}
vector<vi>res;
while((int)roots.size() > 0) {
//for(int i = 0; i < n; ++i) {
//cout << p[i] << " ";
//}
//cout << "\n";
int x = roots.back();
if(edges[x].size() == 0) {
res.PB(vertices[x]);
roots.pop_back();
continue;
}
int y = edges[x].back();
edges[x].pop_back();
if(p[x] == p[y]) continue;
//cout << "MERGING: " << x << " " << y << "\n";
x = p[x]; y = p[y];
if(!Onion(x, y)) {
//cout << "OPT1\n";
vi path = {y};
while(p[par[y]] != x) {
//cerr << p[par[y]] << " " << x << "\n";
path.PB(p[par[y]]);
y = p[par[y]];
}
path.PB(x);
for(int j = 1; j < (int)path.size(); ++j) {
merge(path[j], path[j - 1]);
}
roots.pop_back();
roots.PB(p[path[0]]);
} else {
//cout << "OPT2\n";
par[x] = p[y];
roots.pop_back();
}
}
int mi = 1000000000;
for(auto &vec : res) {
mi = min(mi, (int)vec.size());
}
vi ans(n);
for(int i = 0; i < n; ++i) ans[i] = 0;
for(auto &vec : res) {
if((int)vec.size() == mi) {
for(int x : vec) {
ans[x] = 1;
}
}
}
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
31 ms |
49604 KB |
Output is correct |
2 |
Correct |
32 ms |
49592 KB |
Output is correct |
3 |
Correct |
31 ms |
49612 KB |
Output is correct |
4 |
Correct |
31 ms |
49632 KB |
Output is correct |
5 |
Correct |
31 ms |
49540 KB |
Output is correct |
6 |
Correct |
35 ms |
49576 KB |
Output is correct |
7 |
Correct |
31 ms |
49556 KB |
Output is correct |
8 |
Correct |
32 ms |
49612 KB |
Output is correct |
9 |
Correct |
33 ms |
49672 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
31 ms |
49604 KB |
Output is correct |
2 |
Correct |
32 ms |
49592 KB |
Output is correct |
3 |
Correct |
31 ms |
49612 KB |
Output is correct |
4 |
Correct |
31 ms |
49632 KB |
Output is correct |
5 |
Correct |
31 ms |
49540 KB |
Output is correct |
6 |
Correct |
35 ms |
49576 KB |
Output is correct |
7 |
Correct |
31 ms |
49556 KB |
Output is correct |
8 |
Correct |
32 ms |
49612 KB |
Output is correct |
9 |
Correct |
33 ms |
49672 KB |
Output is correct |
10 |
Correct |
31 ms |
49684 KB |
Output is correct |
11 |
Correct |
31 ms |
49604 KB |
Output is correct |
12 |
Correct |
31 ms |
49700 KB |
Output is correct |
13 |
Correct |
32 ms |
49632 KB |
Output is correct |
14 |
Correct |
31 ms |
49648 KB |
Output is correct |
15 |
Correct |
33 ms |
49640 KB |
Output is correct |
16 |
Correct |
32 ms |
49652 KB |
Output is correct |
17 |
Correct |
36 ms |
49612 KB |
Output is correct |
18 |
Correct |
32 ms |
49612 KB |
Output is correct |
19 |
Correct |
31 ms |
49612 KB |
Output is correct |
20 |
Correct |
33 ms |
49648 KB |
Output is correct |
21 |
Correct |
33 ms |
49696 KB |
Output is correct |
22 |
Correct |
35 ms |
49676 KB |
Output is correct |
23 |
Correct |
36 ms |
49652 KB |
Output is correct |
24 |
Correct |
31 ms |
49712 KB |
Output is correct |
25 |
Correct |
33 ms |
49756 KB |
Output is correct |
26 |
Correct |
32 ms |
49580 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
31 ms |
49604 KB |
Output is correct |
2 |
Correct |
32 ms |
49592 KB |
Output is correct |
3 |
Correct |
31 ms |
49612 KB |
Output is correct |
4 |
Correct |
31 ms |
49632 KB |
Output is correct |
5 |
Correct |
31 ms |
49540 KB |
Output is correct |
6 |
Correct |
35 ms |
49576 KB |
Output is correct |
7 |
Correct |
31 ms |
49556 KB |
Output is correct |
8 |
Correct |
32 ms |
49612 KB |
Output is correct |
9 |
Correct |
33 ms |
49672 KB |
Output is correct |
10 |
Correct |
31 ms |
49684 KB |
Output is correct |
11 |
Correct |
31 ms |
49604 KB |
Output is correct |
12 |
Correct |
31 ms |
49700 KB |
Output is correct |
13 |
Correct |
32 ms |
49632 KB |
Output is correct |
14 |
Correct |
31 ms |
49648 KB |
Output is correct |
15 |
Correct |
33 ms |
49640 KB |
Output is correct |
16 |
Correct |
32 ms |
49652 KB |
Output is correct |
17 |
Correct |
36 ms |
49612 KB |
Output is correct |
18 |
Correct |
32 ms |
49612 KB |
Output is correct |
19 |
Correct |
31 ms |
49612 KB |
Output is correct |
20 |
Correct |
33 ms |
49648 KB |
Output is correct |
21 |
Correct |
33 ms |
49696 KB |
Output is correct |
22 |
Correct |
35 ms |
49676 KB |
Output is correct |
23 |
Correct |
36 ms |
49652 KB |
Output is correct |
24 |
Correct |
31 ms |
49712 KB |
Output is correct |
25 |
Correct |
33 ms |
49756 KB |
Output is correct |
26 |
Correct |
32 ms |
49580 KB |
Output is correct |
27 |
Correct |
34 ms |
50468 KB |
Output is correct |
28 |
Correct |
33 ms |
50412 KB |
Output is correct |
29 |
Correct |
33 ms |
50344 KB |
Output is correct |
30 |
Correct |
39 ms |
49996 KB |
Output is correct |
31 |
Correct |
32 ms |
49928 KB |
Output is correct |
32 |
Correct |
34 ms |
49692 KB |
Output is correct |
33 |
Correct |
33 ms |
49932 KB |
Output is correct |
34 |
Correct |
33 ms |
50032 KB |
Output is correct |
35 |
Correct |
32 ms |
49928 KB |
Output is correct |
36 |
Correct |
33 ms |
50256 KB |
Output is correct |
37 |
Correct |
34 ms |
50312 KB |
Output is correct |
38 |
Correct |
34 ms |
50372 KB |
Output is correct |
39 |
Correct |
34 ms |
50356 KB |
Output is correct |
40 |
Correct |
33 ms |
50124 KB |
Output is correct |
41 |
Correct |
39 ms |
50288 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
31 ms |
49604 KB |
Output is correct |
2 |
Correct |
32 ms |
49592 KB |
Output is correct |
3 |
Correct |
31 ms |
49612 KB |
Output is correct |
4 |
Correct |
31 ms |
49632 KB |
Output is correct |
5 |
Correct |
31 ms |
49540 KB |
Output is correct |
6 |
Correct |
35 ms |
49576 KB |
Output is correct |
7 |
Correct |
31 ms |
49556 KB |
Output is correct |
8 |
Correct |
32 ms |
49612 KB |
Output is correct |
9 |
Correct |
33 ms |
49672 KB |
Output is correct |
10 |
Correct |
378 ms |
130744 KB |
Output is correct |
11 |
Correct |
719 ms |
150016 KB |
Output is correct |
12 |
Correct |
170 ms |
74436 KB |
Output is correct |
13 |
Correct |
933 ms |
172352 KB |
Output is correct |
14 |
Correct |
421 ms |
159376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
31 ms |
49604 KB |
Output is correct |
2 |
Correct |
32 ms |
49592 KB |
Output is correct |
3 |
Correct |
31 ms |
49612 KB |
Output is correct |
4 |
Correct |
31 ms |
49632 KB |
Output is correct |
5 |
Correct |
31 ms |
49540 KB |
Output is correct |
6 |
Correct |
35 ms |
49576 KB |
Output is correct |
7 |
Correct |
31 ms |
49556 KB |
Output is correct |
8 |
Correct |
32 ms |
49612 KB |
Output is correct |
9 |
Correct |
33 ms |
49672 KB |
Output is correct |
10 |
Correct |
31 ms |
49684 KB |
Output is correct |
11 |
Correct |
31 ms |
49604 KB |
Output is correct |
12 |
Correct |
31 ms |
49700 KB |
Output is correct |
13 |
Correct |
32 ms |
49632 KB |
Output is correct |
14 |
Correct |
31 ms |
49648 KB |
Output is correct |
15 |
Correct |
33 ms |
49640 KB |
Output is correct |
16 |
Correct |
32 ms |
49652 KB |
Output is correct |
17 |
Correct |
36 ms |
49612 KB |
Output is correct |
18 |
Correct |
32 ms |
49612 KB |
Output is correct |
19 |
Correct |
31 ms |
49612 KB |
Output is correct |
20 |
Correct |
33 ms |
49648 KB |
Output is correct |
21 |
Correct |
33 ms |
49696 KB |
Output is correct |
22 |
Correct |
35 ms |
49676 KB |
Output is correct |
23 |
Correct |
36 ms |
49652 KB |
Output is correct |
24 |
Correct |
31 ms |
49712 KB |
Output is correct |
25 |
Correct |
33 ms |
49756 KB |
Output is correct |
26 |
Correct |
32 ms |
49580 KB |
Output is correct |
27 |
Correct |
34 ms |
50468 KB |
Output is correct |
28 |
Correct |
33 ms |
50412 KB |
Output is correct |
29 |
Correct |
33 ms |
50344 KB |
Output is correct |
30 |
Correct |
39 ms |
49996 KB |
Output is correct |
31 |
Correct |
32 ms |
49928 KB |
Output is correct |
32 |
Correct |
34 ms |
49692 KB |
Output is correct |
33 |
Correct |
33 ms |
49932 KB |
Output is correct |
34 |
Correct |
33 ms |
50032 KB |
Output is correct |
35 |
Correct |
32 ms |
49928 KB |
Output is correct |
36 |
Correct |
33 ms |
50256 KB |
Output is correct |
37 |
Correct |
34 ms |
50312 KB |
Output is correct |
38 |
Correct |
34 ms |
50372 KB |
Output is correct |
39 |
Correct |
34 ms |
50356 KB |
Output is correct |
40 |
Correct |
33 ms |
50124 KB |
Output is correct |
41 |
Correct |
39 ms |
50288 KB |
Output is correct |
42 |
Correct |
378 ms |
130744 KB |
Output is correct |
43 |
Correct |
719 ms |
150016 KB |
Output is correct |
44 |
Correct |
170 ms |
74436 KB |
Output is correct |
45 |
Correct |
933 ms |
172352 KB |
Output is correct |
46 |
Correct |
421 ms |
159376 KB |
Output is correct |
47 |
Correct |
31 ms |
49544 KB |
Output is correct |
48 |
Correct |
31 ms |
49612 KB |
Output is correct |
49 |
Correct |
31 ms |
49588 KB |
Output is correct |
50 |
Correct |
402 ms |
157748 KB |
Output is correct |
51 |
Correct |
396 ms |
151352 KB |
Output is correct |
52 |
Correct |
376 ms |
137228 KB |
Output is correct |
53 |
Correct |
407 ms |
137332 KB |
Output is correct |
54 |
Correct |
394 ms |
137276 KB |
Output is correct |
55 |
Correct |
388 ms |
143312 KB |
Output is correct |
56 |
Correct |
584 ms |
161300 KB |
Output is correct |
57 |
Correct |
396 ms |
144456 KB |
Output is correct |
58 |
Correct |
673 ms |
184236 KB |
Output is correct |
59 |
Correct |
1585 ms |
171752 KB |
Output is correct |
60 |
Correct |
527 ms |
158972 KB |
Output is correct |
61 |
Correct |
508 ms |
159252 KB |
Output is correct |
62 |
Correct |
437 ms |
146828 KB |
Output is correct |
63 |
Correct |
561 ms |
152352 KB |
Output is correct |
64 |
Correct |
43 ms |
51396 KB |
Output is correct |
65 |
Correct |
38 ms |
51488 KB |
Output is correct |
66 |
Correct |
426 ms |
146820 KB |
Output is correct |
67 |
Correct |
76 ms |
60168 KB |
Output is correct |
68 |
Correct |
96 ms |
67392 KB |
Output is correct |
69 |
Correct |
1576 ms |
171344 KB |
Output is correct |
70 |
Correct |
160 ms |
85312 KB |
Output is correct |
71 |
Correct |
426 ms |
159880 KB |
Output is correct |
72 |
Correct |
1572 ms |
171396 KB |
Output is correct |
73 |
Correct |
421 ms |
146824 KB |
Output is correct |