# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
621471 |
2022-08-03T20:50:00 Z |
penguinhacker |
Keys (IOI21_keys) |
C++17 |
|
1171 ms |
50120 KB |
#include <bits/stdc++.h>
using namespace std;
#define ar array
const int mxN=3e5;
int n, m, sz[mxN], p[mxN];
vector<ar<int, 2>> adj[mxN];
bool dead[mxN], vis[mxN], has_key[mxN];
vector<int> by_color[mxN];
int find(int i) {
return i^p[i]?p[i]=find(p[i]):i;
}
vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
int n=r.size(), m=u.size();
for (int i=0; i<m; ++i) {
adj[u[i]].push_back({v[i], c[i]});
adj[v[i]].push_back({u[i], c[i]});
}
memset(sz, 0x3f, sizeof(sz));
iota(p, p+n, 0);
while(count(dead, dead+n, 0)) {
vector<ar<int, 2>> todo;
for (int i=0; i<n; ++i) {
if (dead[i])
continue;
vector<int> cmp(1, i);
vis[i]=1;
int found=-1;
for (int j=0; j<cmp.size()&&found==-1; ++j) {
int u=cmp[j];
has_key[r[u]]=1;
auto ck=[&](int v) {
if (!vis[v]&&found==-1) {
if (find(v)!=find(i))
found=find(v);
else {
cmp.push_back(v);
vis[v]=1;
}
}
};
for (int v : by_color[r[u]])
ck(v);
by_color[r[u]].clear();
for (ar<int, 2> v : adj[u]) {
if (has_key[v[1]])
ck(v[0]);
else
by_color[v[1]].push_back(v[0]);
}
}
if (found==-1) {
dead[i]=1;
for (int j : cmp)
sz[j]=cmp.size();
} else if (dead[found]) {
dead[i]=1;
} else {
todo.push_back({i, found});
}
for (int j : cmp) {
vis[j]=0;
for (ar<int, 2> v : adj[j])
by_color[v[1]].clear();
has_key[r[j]]=0;
}
}
for (auto [u, v] : todo) {
if (find(u)!=find(v)) {
p[u]=v;
dead[u]=1;
}
}
}
int mn=*min_element(sz, sz+n);
vector<int> ans(n);
for (int i=0; i<n; ++i)
ans[i]=sz[i]==mn;
return ans;
}
Compilation message
keys.cpp: In function 'std::vector<int> find_reachable(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
keys.cpp:32:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
32 | for (int j=0; j<cmp.size()&&found==-1; ++j) {
| ~^~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
15480 KB |
Output is correct |
2 |
Correct |
8 ms |
15572 KB |
Output is correct |
3 |
Correct |
8 ms |
15572 KB |
Output is correct |
4 |
Correct |
9 ms |
15572 KB |
Output is correct |
5 |
Correct |
10 ms |
15572 KB |
Output is correct |
6 |
Correct |
9 ms |
15572 KB |
Output is correct |
7 |
Correct |
8 ms |
15588 KB |
Output is correct |
8 |
Correct |
8 ms |
15576 KB |
Output is correct |
9 |
Correct |
9 ms |
15572 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
15480 KB |
Output is correct |
2 |
Correct |
8 ms |
15572 KB |
Output is correct |
3 |
Correct |
8 ms |
15572 KB |
Output is correct |
4 |
Correct |
9 ms |
15572 KB |
Output is correct |
5 |
Correct |
10 ms |
15572 KB |
Output is correct |
6 |
Correct |
9 ms |
15572 KB |
Output is correct |
7 |
Correct |
8 ms |
15588 KB |
Output is correct |
8 |
Correct |
8 ms |
15576 KB |
Output is correct |
9 |
Correct |
9 ms |
15572 KB |
Output is correct |
10 |
Correct |
9 ms |
15572 KB |
Output is correct |
11 |
Correct |
10 ms |
15560 KB |
Output is correct |
12 |
Correct |
9 ms |
15572 KB |
Output is correct |
13 |
Correct |
10 ms |
15572 KB |
Output is correct |
14 |
Correct |
8 ms |
15572 KB |
Output is correct |
15 |
Correct |
8 ms |
15572 KB |
Output is correct |
16 |
Correct |
8 ms |
15572 KB |
Output is correct |
17 |
Correct |
10 ms |
15592 KB |
Output is correct |
18 |
Correct |
8 ms |
15572 KB |
Output is correct |
19 |
Correct |
8 ms |
15572 KB |
Output is correct |
20 |
Correct |
8 ms |
15572 KB |
Output is correct |
21 |
Correct |
10 ms |
15572 KB |
Output is correct |
22 |
Correct |
8 ms |
15596 KB |
Output is correct |
23 |
Correct |
8 ms |
15528 KB |
Output is correct |
24 |
Correct |
9 ms |
15572 KB |
Output is correct |
25 |
Correct |
9 ms |
15492 KB |
Output is correct |
26 |
Correct |
11 ms |
15484 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
15480 KB |
Output is correct |
2 |
Correct |
8 ms |
15572 KB |
Output is correct |
3 |
Correct |
8 ms |
15572 KB |
Output is correct |
4 |
Correct |
9 ms |
15572 KB |
Output is correct |
5 |
Correct |
10 ms |
15572 KB |
Output is correct |
6 |
Correct |
9 ms |
15572 KB |
Output is correct |
7 |
Correct |
8 ms |
15588 KB |
Output is correct |
8 |
Correct |
8 ms |
15576 KB |
Output is correct |
9 |
Correct |
9 ms |
15572 KB |
Output is correct |
10 |
Correct |
9 ms |
15572 KB |
Output is correct |
11 |
Correct |
10 ms |
15560 KB |
Output is correct |
12 |
Correct |
9 ms |
15572 KB |
Output is correct |
13 |
Correct |
10 ms |
15572 KB |
Output is correct |
14 |
Correct |
8 ms |
15572 KB |
Output is correct |
15 |
Correct |
8 ms |
15572 KB |
Output is correct |
16 |
Correct |
8 ms |
15572 KB |
Output is correct |
17 |
Correct |
10 ms |
15592 KB |
Output is correct |
18 |
Correct |
8 ms |
15572 KB |
Output is correct |
19 |
Correct |
8 ms |
15572 KB |
Output is correct |
20 |
Correct |
8 ms |
15572 KB |
Output is correct |
21 |
Correct |
10 ms |
15572 KB |
Output is correct |
22 |
Correct |
8 ms |
15596 KB |
Output is correct |
23 |
Correct |
8 ms |
15528 KB |
Output is correct |
24 |
Correct |
9 ms |
15572 KB |
Output is correct |
25 |
Correct |
9 ms |
15492 KB |
Output is correct |
26 |
Correct |
11 ms |
15484 KB |
Output is correct |
27 |
Correct |
10 ms |
15700 KB |
Output is correct |
28 |
Correct |
10 ms |
15720 KB |
Output is correct |
29 |
Correct |
9 ms |
15700 KB |
Output is correct |
30 |
Correct |
10 ms |
15564 KB |
Output is correct |
31 |
Correct |
8 ms |
15600 KB |
Output is correct |
32 |
Correct |
10 ms |
15572 KB |
Output is correct |
33 |
Correct |
10 ms |
15668 KB |
Output is correct |
34 |
Correct |
9 ms |
15572 KB |
Output is correct |
35 |
Correct |
8 ms |
15676 KB |
Output is correct |
36 |
Correct |
11 ms |
15700 KB |
Output is correct |
37 |
Correct |
12 ms |
15704 KB |
Output is correct |
38 |
Correct |
9 ms |
15700 KB |
Output is correct |
39 |
Correct |
10 ms |
15700 KB |
Output is correct |
40 |
Correct |
9 ms |
15672 KB |
Output is correct |
41 |
Correct |
10 ms |
15700 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
15480 KB |
Output is correct |
2 |
Correct |
8 ms |
15572 KB |
Output is correct |
3 |
Correct |
8 ms |
15572 KB |
Output is correct |
4 |
Correct |
9 ms |
15572 KB |
Output is correct |
5 |
Correct |
10 ms |
15572 KB |
Output is correct |
6 |
Correct |
9 ms |
15572 KB |
Output is correct |
7 |
Correct |
8 ms |
15588 KB |
Output is correct |
8 |
Correct |
8 ms |
15576 KB |
Output is correct |
9 |
Correct |
9 ms |
15572 KB |
Output is correct |
10 |
Correct |
199 ms |
34972 KB |
Output is correct |
11 |
Correct |
257 ms |
45896 KB |
Output is correct |
12 |
Correct |
52 ms |
20308 KB |
Output is correct |
13 |
Correct |
280 ms |
39228 KB |
Output is correct |
14 |
Correct |
180 ms |
39940 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
15480 KB |
Output is correct |
2 |
Correct |
8 ms |
15572 KB |
Output is correct |
3 |
Correct |
8 ms |
15572 KB |
Output is correct |
4 |
Correct |
9 ms |
15572 KB |
Output is correct |
5 |
Correct |
10 ms |
15572 KB |
Output is correct |
6 |
Correct |
9 ms |
15572 KB |
Output is correct |
7 |
Correct |
8 ms |
15588 KB |
Output is correct |
8 |
Correct |
8 ms |
15576 KB |
Output is correct |
9 |
Correct |
9 ms |
15572 KB |
Output is correct |
10 |
Correct |
9 ms |
15572 KB |
Output is correct |
11 |
Correct |
10 ms |
15560 KB |
Output is correct |
12 |
Correct |
9 ms |
15572 KB |
Output is correct |
13 |
Correct |
10 ms |
15572 KB |
Output is correct |
14 |
Correct |
8 ms |
15572 KB |
Output is correct |
15 |
Correct |
8 ms |
15572 KB |
Output is correct |
16 |
Correct |
8 ms |
15572 KB |
Output is correct |
17 |
Correct |
10 ms |
15592 KB |
Output is correct |
18 |
Correct |
8 ms |
15572 KB |
Output is correct |
19 |
Correct |
8 ms |
15572 KB |
Output is correct |
20 |
Correct |
8 ms |
15572 KB |
Output is correct |
21 |
Correct |
10 ms |
15572 KB |
Output is correct |
22 |
Correct |
8 ms |
15596 KB |
Output is correct |
23 |
Correct |
8 ms |
15528 KB |
Output is correct |
24 |
Correct |
9 ms |
15572 KB |
Output is correct |
25 |
Correct |
9 ms |
15492 KB |
Output is correct |
26 |
Correct |
11 ms |
15484 KB |
Output is correct |
27 |
Correct |
10 ms |
15700 KB |
Output is correct |
28 |
Correct |
10 ms |
15720 KB |
Output is correct |
29 |
Correct |
9 ms |
15700 KB |
Output is correct |
30 |
Correct |
10 ms |
15564 KB |
Output is correct |
31 |
Correct |
8 ms |
15600 KB |
Output is correct |
32 |
Correct |
10 ms |
15572 KB |
Output is correct |
33 |
Correct |
10 ms |
15668 KB |
Output is correct |
34 |
Correct |
9 ms |
15572 KB |
Output is correct |
35 |
Correct |
8 ms |
15676 KB |
Output is correct |
36 |
Correct |
11 ms |
15700 KB |
Output is correct |
37 |
Correct |
12 ms |
15704 KB |
Output is correct |
38 |
Correct |
9 ms |
15700 KB |
Output is correct |
39 |
Correct |
10 ms |
15700 KB |
Output is correct |
40 |
Correct |
9 ms |
15672 KB |
Output is correct |
41 |
Correct |
10 ms |
15700 KB |
Output is correct |
42 |
Correct |
199 ms |
34972 KB |
Output is correct |
43 |
Correct |
257 ms |
45896 KB |
Output is correct |
44 |
Correct |
52 ms |
20308 KB |
Output is correct |
45 |
Correct |
280 ms |
39228 KB |
Output is correct |
46 |
Correct |
180 ms |
39940 KB |
Output is correct |
47 |
Correct |
9 ms |
15572 KB |
Output is correct |
48 |
Correct |
8 ms |
15588 KB |
Output is correct |
49 |
Correct |
9 ms |
15556 KB |
Output is correct |
50 |
Correct |
155 ms |
41192 KB |
Output is correct |
51 |
Correct |
181 ms |
40548 KB |
Output is correct |
52 |
Correct |
214 ms |
38124 KB |
Output is correct |
53 |
Correct |
220 ms |
38144 KB |
Output is correct |
54 |
Correct |
228 ms |
38084 KB |
Output is correct |
55 |
Correct |
248 ms |
35136 KB |
Output is correct |
56 |
Correct |
302 ms |
43204 KB |
Output is correct |
57 |
Correct |
234 ms |
39804 KB |
Output is correct |
58 |
Correct |
273 ms |
50120 KB |
Output is correct |
59 |
Correct |
405 ms |
43260 KB |
Output is correct |
60 |
Correct |
349 ms |
43552 KB |
Output is correct |
61 |
Correct |
344 ms |
44264 KB |
Output is correct |
62 |
Correct |
1171 ms |
40484 KB |
Output is correct |
63 |
Correct |
203 ms |
39376 KB |
Output is correct |
64 |
Correct |
12 ms |
16020 KB |
Output is correct |
65 |
Correct |
12 ms |
15956 KB |
Output is correct |
66 |
Correct |
1090 ms |
40248 KB |
Output is correct |
67 |
Correct |
25 ms |
17960 KB |
Output is correct |
68 |
Correct |
35 ms |
19484 KB |
Output is correct |
69 |
Correct |
377 ms |
43240 KB |
Output is correct |
70 |
Correct |
60 ms |
23400 KB |
Output is correct |
71 |
Correct |
167 ms |
39952 KB |
Output is correct |
72 |
Correct |
390 ms |
43268 KB |
Output is correct |
73 |
Correct |
1103 ms |
40112 KB |
Output is correct |