# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
749106 |
2023-05-27T10:18:48 Z |
numberes |
Keys (IOI21_keys) |
C++17 |
|
722 ms |
69120 KB |
/**
* @date 2023-05-27 16:46:26
* RAmen!
*/
#include<bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pii pair<int, int>
#define ll long long
using namespace std;
int n, key[300005], spe[300005], iss[300005], fa[300005];
vector<int> comp[300005];
int head[300005], nxt[600005], tot;
pii to[600005];
vector<int> col[300005];
bool vis[300005], visc[300005];
vector<int> cl, clc;
int ans; vector<int> out;
int fnd(int x) {
return x == fa[x] ? x : fa[x] = fnd(fa[x]);
}
void add_edge(int u, int v, int w) {
nxt[++tot] = head[u]; head[u] = tot; to[tot] = mp(v, w);
}
void clean() {
for(auto u : cl) vis[u] = 0;
for(auto x : clc) {col[x].clear(); visc[x] = 0;} clc.clear();
}
pii bfs(int s) {
queue<int> q; q.push(s); int num = 1;
cl.pb(s); clc.pb(key[s]); vis[s] = 1;
while(!q.empty()) {
int u = q.front(); q.pop();
if(fnd(u) != fnd(s)) {
clean(); return mp(fnd(u), num);
}
for(auto v : col[key[u]]) if(!vis[v]) {
vis[v] = 1; num++; cl.pb(v); q.push(v);
}
col[key[u]].clear(); visc[key[u]] = 1; clc.pb(key[u]);
pii now = to[head[u]];
for(int i = head[u]; i; i = nxt[i], now = to[i]) if(!vis[now.fi]) {
if(visc[now.se]) {
vis[now.fi] = 1; num++; cl.pb(now.fi); q.push(now.fi);
}
else {
clc.pb(now.se); col[now.se].pb(now.fi);
}
}
}
clean(); return mp(-1, num);
}
void merge(int a, int b) {
if(b == -1 || spe[b] == -1) {
iss[spe[a]] = 0; spe[a] = -1;
return;
}
if(comp[a].size() > comp[b].size()) {
comp[a].insert(comp[a].end(), comp[b].begin(), comp[b].end());
comp[b].clear();
iss[spe[a]] = 0; spe[a] = spe[b]; fa[b] = a;
}
else {
comp[b].insert(comp[b].end(), comp[a].begin(), comp[a].end());
comp[a].clear();
iss[spe[a]] = 0; fa[a] = b;
}
}
vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
for(auto x : r) key[++n] = x + 1;
for(int i = 0; i < (int)u.size(); i++) {
u[i]++; v[i]++; c[i]++;
add_edge(u[i], v[i], c[i]); add_edge(v[i], u[i], c[i]);
}
/*int m; cin >> n >> m;
for(int i = 1; i <= n; i++) {
cin >> key[i]; key[i]++;
}
for(int i = 1; i <= m; i++) {
int u, v, c; cin >> u >> v >> c;
u++; v++; c++;
add_edge(u, v, c); add_edge(v, u, c);
}*/
for(int i = 1; i <= n; i++) {
fa[i] = i; iss[i] = 1; spe[i] = i; comp[i].pb(i);
}
ans = 1e9;
for(int t = 0; t < 25; t++) {
for(int i = 1; i <= n; i++) if(iss[i]) {
pii res = bfs(i);
if(res.fi == -1) {
if(ans > res.se) {
ans = res.se; out = cl;
}
else if(ans == res.se)
out.insert(out.end(), cl.begin(), cl.end());
}
cl.clear();
merge(fnd(i), res.fi);
}
}
vector<int> ret;
for(int i = 1; i <= n; i++)
ret.pb(0);
for(auto x : out) {
// cout << x << endl;
ret[x - 1] = 1;
}
return ret;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
14420 KB |
Output is correct |
2 |
Correct |
8 ms |
14420 KB |
Output is correct |
3 |
Correct |
8 ms |
14420 KB |
Output is correct |
4 |
Correct |
9 ms |
14420 KB |
Output is correct |
5 |
Correct |
8 ms |
14384 KB |
Output is correct |
6 |
Correct |
8 ms |
14348 KB |
Output is correct |
7 |
Correct |
8 ms |
14420 KB |
Output is correct |
8 |
Correct |
8 ms |
14420 KB |
Output is correct |
9 |
Correct |
8 ms |
14420 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
14420 KB |
Output is correct |
2 |
Correct |
8 ms |
14420 KB |
Output is correct |
3 |
Correct |
8 ms |
14420 KB |
Output is correct |
4 |
Correct |
9 ms |
14420 KB |
Output is correct |
5 |
Correct |
8 ms |
14384 KB |
Output is correct |
6 |
Correct |
8 ms |
14348 KB |
Output is correct |
7 |
Correct |
8 ms |
14420 KB |
Output is correct |
8 |
Correct |
8 ms |
14420 KB |
Output is correct |
9 |
Correct |
8 ms |
14420 KB |
Output is correct |
10 |
Correct |
7 ms |
14420 KB |
Output is correct |
11 |
Correct |
7 ms |
14420 KB |
Output is correct |
12 |
Correct |
7 ms |
14420 KB |
Output is correct |
13 |
Correct |
7 ms |
14420 KB |
Output is correct |
14 |
Correct |
8 ms |
14420 KB |
Output is correct |
15 |
Correct |
8 ms |
14468 KB |
Output is correct |
16 |
Correct |
8 ms |
14420 KB |
Output is correct |
17 |
Correct |
8 ms |
14420 KB |
Output is correct |
18 |
Correct |
8 ms |
14420 KB |
Output is correct |
19 |
Correct |
8 ms |
14352 KB |
Output is correct |
20 |
Correct |
8 ms |
14420 KB |
Output is correct |
21 |
Correct |
8 ms |
14420 KB |
Output is correct |
22 |
Correct |
8 ms |
14420 KB |
Output is correct |
23 |
Correct |
8 ms |
14420 KB |
Output is correct |
24 |
Correct |
8 ms |
14476 KB |
Output is correct |
25 |
Correct |
8 ms |
14420 KB |
Output is correct |
26 |
Correct |
8 ms |
14420 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
14420 KB |
Output is correct |
2 |
Correct |
8 ms |
14420 KB |
Output is correct |
3 |
Correct |
8 ms |
14420 KB |
Output is correct |
4 |
Correct |
9 ms |
14420 KB |
Output is correct |
5 |
Correct |
8 ms |
14384 KB |
Output is correct |
6 |
Correct |
8 ms |
14348 KB |
Output is correct |
7 |
Correct |
8 ms |
14420 KB |
Output is correct |
8 |
Correct |
8 ms |
14420 KB |
Output is correct |
9 |
Correct |
8 ms |
14420 KB |
Output is correct |
10 |
Correct |
7 ms |
14420 KB |
Output is correct |
11 |
Correct |
7 ms |
14420 KB |
Output is correct |
12 |
Correct |
7 ms |
14420 KB |
Output is correct |
13 |
Correct |
7 ms |
14420 KB |
Output is correct |
14 |
Correct |
8 ms |
14420 KB |
Output is correct |
15 |
Correct |
8 ms |
14468 KB |
Output is correct |
16 |
Correct |
8 ms |
14420 KB |
Output is correct |
17 |
Correct |
8 ms |
14420 KB |
Output is correct |
18 |
Correct |
8 ms |
14420 KB |
Output is correct |
19 |
Correct |
8 ms |
14352 KB |
Output is correct |
20 |
Correct |
8 ms |
14420 KB |
Output is correct |
21 |
Correct |
8 ms |
14420 KB |
Output is correct |
22 |
Correct |
8 ms |
14420 KB |
Output is correct |
23 |
Correct |
8 ms |
14420 KB |
Output is correct |
24 |
Correct |
8 ms |
14476 KB |
Output is correct |
25 |
Correct |
8 ms |
14420 KB |
Output is correct |
26 |
Correct |
8 ms |
14420 KB |
Output is correct |
27 |
Correct |
8 ms |
14676 KB |
Output is correct |
28 |
Correct |
8 ms |
14676 KB |
Output is correct |
29 |
Correct |
9 ms |
14676 KB |
Output is correct |
30 |
Correct |
10 ms |
14556 KB |
Output is correct |
31 |
Correct |
10 ms |
14516 KB |
Output is correct |
32 |
Correct |
8 ms |
14480 KB |
Output is correct |
33 |
Correct |
8 ms |
14548 KB |
Output is correct |
34 |
Correct |
8 ms |
14548 KB |
Output is correct |
35 |
Correct |
9 ms |
14548 KB |
Output is correct |
36 |
Correct |
9 ms |
14676 KB |
Output is correct |
37 |
Correct |
9 ms |
14676 KB |
Output is correct |
38 |
Correct |
8 ms |
14744 KB |
Output is correct |
39 |
Correct |
9 ms |
14804 KB |
Output is correct |
40 |
Correct |
8 ms |
14548 KB |
Output is correct |
41 |
Correct |
9 ms |
14548 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
14420 KB |
Output is correct |
2 |
Correct |
8 ms |
14420 KB |
Output is correct |
3 |
Correct |
8 ms |
14420 KB |
Output is correct |
4 |
Correct |
9 ms |
14420 KB |
Output is correct |
5 |
Correct |
8 ms |
14384 KB |
Output is correct |
6 |
Correct |
8 ms |
14348 KB |
Output is correct |
7 |
Correct |
8 ms |
14420 KB |
Output is correct |
8 |
Correct |
8 ms |
14420 KB |
Output is correct |
9 |
Correct |
8 ms |
14420 KB |
Output is correct |
10 |
Correct |
257 ms |
39816 KB |
Output is correct |
11 |
Correct |
216 ms |
55964 KB |
Output is correct |
12 |
Correct |
48 ms |
20804 KB |
Output is correct |
13 |
Correct |
285 ms |
47928 KB |
Output is correct |
14 |
Correct |
178 ms |
54944 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
14420 KB |
Output is correct |
2 |
Correct |
8 ms |
14420 KB |
Output is correct |
3 |
Correct |
8 ms |
14420 KB |
Output is correct |
4 |
Correct |
9 ms |
14420 KB |
Output is correct |
5 |
Correct |
8 ms |
14384 KB |
Output is correct |
6 |
Correct |
8 ms |
14348 KB |
Output is correct |
7 |
Correct |
8 ms |
14420 KB |
Output is correct |
8 |
Correct |
8 ms |
14420 KB |
Output is correct |
9 |
Correct |
8 ms |
14420 KB |
Output is correct |
10 |
Correct |
7 ms |
14420 KB |
Output is correct |
11 |
Correct |
7 ms |
14420 KB |
Output is correct |
12 |
Correct |
7 ms |
14420 KB |
Output is correct |
13 |
Correct |
7 ms |
14420 KB |
Output is correct |
14 |
Correct |
8 ms |
14420 KB |
Output is correct |
15 |
Correct |
8 ms |
14468 KB |
Output is correct |
16 |
Correct |
8 ms |
14420 KB |
Output is correct |
17 |
Correct |
8 ms |
14420 KB |
Output is correct |
18 |
Correct |
8 ms |
14420 KB |
Output is correct |
19 |
Correct |
8 ms |
14352 KB |
Output is correct |
20 |
Correct |
8 ms |
14420 KB |
Output is correct |
21 |
Correct |
8 ms |
14420 KB |
Output is correct |
22 |
Correct |
8 ms |
14420 KB |
Output is correct |
23 |
Correct |
8 ms |
14420 KB |
Output is correct |
24 |
Correct |
8 ms |
14476 KB |
Output is correct |
25 |
Correct |
8 ms |
14420 KB |
Output is correct |
26 |
Correct |
8 ms |
14420 KB |
Output is correct |
27 |
Correct |
8 ms |
14676 KB |
Output is correct |
28 |
Correct |
8 ms |
14676 KB |
Output is correct |
29 |
Correct |
9 ms |
14676 KB |
Output is correct |
30 |
Correct |
10 ms |
14556 KB |
Output is correct |
31 |
Correct |
10 ms |
14516 KB |
Output is correct |
32 |
Correct |
8 ms |
14480 KB |
Output is correct |
33 |
Correct |
8 ms |
14548 KB |
Output is correct |
34 |
Correct |
8 ms |
14548 KB |
Output is correct |
35 |
Correct |
9 ms |
14548 KB |
Output is correct |
36 |
Correct |
9 ms |
14676 KB |
Output is correct |
37 |
Correct |
9 ms |
14676 KB |
Output is correct |
38 |
Correct |
8 ms |
14744 KB |
Output is correct |
39 |
Correct |
9 ms |
14804 KB |
Output is correct |
40 |
Correct |
8 ms |
14548 KB |
Output is correct |
41 |
Correct |
9 ms |
14548 KB |
Output is correct |
42 |
Correct |
257 ms |
39816 KB |
Output is correct |
43 |
Correct |
216 ms |
55964 KB |
Output is correct |
44 |
Correct |
48 ms |
20804 KB |
Output is correct |
45 |
Correct |
285 ms |
47928 KB |
Output is correct |
46 |
Correct |
178 ms |
54944 KB |
Output is correct |
47 |
Correct |
8 ms |
14336 KB |
Output is correct |
48 |
Correct |
8 ms |
14344 KB |
Output is correct |
49 |
Correct |
8 ms |
14372 KB |
Output is correct |
50 |
Correct |
187 ms |
54176 KB |
Output is correct |
51 |
Correct |
202 ms |
61888 KB |
Output is correct |
52 |
Correct |
257 ms |
48712 KB |
Output is correct |
53 |
Correct |
240 ms |
48772 KB |
Output is correct |
54 |
Correct |
240 ms |
48768 KB |
Output is correct |
55 |
Correct |
308 ms |
46404 KB |
Output is correct |
56 |
Correct |
342 ms |
64948 KB |
Output is correct |
57 |
Correct |
224 ms |
60044 KB |
Output is correct |
58 |
Correct |
266 ms |
69120 KB |
Output is correct |
59 |
Correct |
473 ms |
63496 KB |
Output is correct |
60 |
Correct |
370 ms |
60132 KB |
Output is correct |
61 |
Correct |
482 ms |
64616 KB |
Output is correct |
62 |
Correct |
721 ms |
53108 KB |
Output is correct |
63 |
Correct |
169 ms |
51836 KB |
Output is correct |
64 |
Correct |
11 ms |
15216 KB |
Output is correct |
65 |
Correct |
11 ms |
15188 KB |
Output is correct |
66 |
Correct |
722 ms |
52884 KB |
Output is correct |
67 |
Correct |
25 ms |
18940 KB |
Output is correct |
68 |
Correct |
39 ms |
21848 KB |
Output is correct |
69 |
Correct |
470 ms |
63748 KB |
Output is correct |
70 |
Correct |
69 ms |
29392 KB |
Output is correct |
71 |
Correct |
190 ms |
60988 KB |
Output is correct |
72 |
Correct |
474 ms |
63940 KB |
Output is correct |
73 |
Correct |
688 ms |
52416 KB |
Output is correct |