# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
621470 |
2022-08-03T20:49:08 Z |
penguinhacker |
Keys (IOI21_keys) |
C++17 |
|
1333 ms |
58092 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]) {
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 |
15572 KB |
Output is correct |
2 |
Correct |
8 ms |
15572 KB |
Output is correct |
3 |
Correct |
11 ms |
15572 KB |
Output is correct |
4 |
Correct |
11 ms |
15572 KB |
Output is correct |
5 |
Correct |
8 ms |
15572 KB |
Output is correct |
6 |
Correct |
8 ms |
15572 KB |
Output is correct |
7 |
Correct |
9 ms |
15492 KB |
Output is correct |
8 |
Correct |
8 ms |
15572 KB |
Output is correct |
9 |
Correct |
8 ms |
15616 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
15572 KB |
Output is correct |
2 |
Correct |
8 ms |
15572 KB |
Output is correct |
3 |
Correct |
11 ms |
15572 KB |
Output is correct |
4 |
Correct |
11 ms |
15572 KB |
Output is correct |
5 |
Correct |
8 ms |
15572 KB |
Output is correct |
6 |
Correct |
8 ms |
15572 KB |
Output is correct |
7 |
Correct |
9 ms |
15492 KB |
Output is correct |
8 |
Correct |
8 ms |
15572 KB |
Output is correct |
9 |
Correct |
8 ms |
15616 KB |
Output is correct |
10 |
Correct |
8 ms |
15572 KB |
Output is correct |
11 |
Correct |
9 ms |
15492 KB |
Output is correct |
12 |
Correct |
8 ms |
15572 KB |
Output is correct |
13 |
Correct |
9 ms |
15568 KB |
Output is correct |
14 |
Correct |
10 ms |
15520 KB |
Output is correct |
15 |
Correct |
10 ms |
15608 KB |
Output is correct |
16 |
Correct |
10 ms |
15540 KB |
Output is correct |
17 |
Correct |
10 ms |
15572 KB |
Output is correct |
18 |
Correct |
9 ms |
15572 KB |
Output is correct |
19 |
Correct |
11 ms |
15572 KB |
Output is correct |
20 |
Correct |
10 ms |
15572 KB |
Output is correct |
21 |
Correct |
10 ms |
15492 KB |
Output is correct |
22 |
Correct |
8 ms |
15572 KB |
Output is correct |
23 |
Correct |
8 ms |
15572 KB |
Output is correct |
24 |
Correct |
9 ms |
15504 KB |
Output is correct |
25 |
Correct |
9 ms |
15572 KB |
Output is correct |
26 |
Correct |
10 ms |
15572 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
15572 KB |
Output is correct |
2 |
Correct |
8 ms |
15572 KB |
Output is correct |
3 |
Correct |
11 ms |
15572 KB |
Output is correct |
4 |
Correct |
11 ms |
15572 KB |
Output is correct |
5 |
Correct |
8 ms |
15572 KB |
Output is correct |
6 |
Correct |
8 ms |
15572 KB |
Output is correct |
7 |
Correct |
9 ms |
15492 KB |
Output is correct |
8 |
Correct |
8 ms |
15572 KB |
Output is correct |
9 |
Correct |
8 ms |
15616 KB |
Output is correct |
10 |
Correct |
8 ms |
15572 KB |
Output is correct |
11 |
Correct |
9 ms |
15492 KB |
Output is correct |
12 |
Correct |
8 ms |
15572 KB |
Output is correct |
13 |
Correct |
9 ms |
15568 KB |
Output is correct |
14 |
Correct |
10 ms |
15520 KB |
Output is correct |
15 |
Correct |
10 ms |
15608 KB |
Output is correct |
16 |
Correct |
10 ms |
15540 KB |
Output is correct |
17 |
Correct |
10 ms |
15572 KB |
Output is correct |
18 |
Correct |
9 ms |
15572 KB |
Output is correct |
19 |
Correct |
11 ms |
15572 KB |
Output is correct |
20 |
Correct |
10 ms |
15572 KB |
Output is correct |
21 |
Correct |
10 ms |
15492 KB |
Output is correct |
22 |
Correct |
8 ms |
15572 KB |
Output is correct |
23 |
Correct |
8 ms |
15572 KB |
Output is correct |
24 |
Correct |
9 ms |
15504 KB |
Output is correct |
25 |
Correct |
9 ms |
15572 KB |
Output is correct |
26 |
Correct |
10 ms |
15572 KB |
Output is correct |
27 |
Correct |
9 ms |
15700 KB |
Output is correct |
28 |
Correct |
12 ms |
15772 KB |
Output is correct |
29 |
Correct |
13 ms |
15692 KB |
Output is correct |
30 |
Correct |
11 ms |
15572 KB |
Output is correct |
31 |
Correct |
11 ms |
15572 KB |
Output is correct |
32 |
Correct |
11 ms |
15628 KB |
Output is correct |
33 |
Correct |
10 ms |
15564 KB |
Output is correct |
34 |
Correct |
10 ms |
15572 KB |
Output is correct |
35 |
Correct |
9 ms |
15572 KB |
Output is correct |
36 |
Correct |
9 ms |
15712 KB |
Output is correct |
37 |
Correct |
9 ms |
15700 KB |
Output is correct |
38 |
Correct |
10 ms |
15700 KB |
Output is correct |
39 |
Correct |
10 ms |
15748 KB |
Output is correct |
40 |
Correct |
13 ms |
15572 KB |
Output is correct |
41 |
Correct |
13 ms |
15700 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
15572 KB |
Output is correct |
2 |
Correct |
8 ms |
15572 KB |
Output is correct |
3 |
Correct |
11 ms |
15572 KB |
Output is correct |
4 |
Correct |
11 ms |
15572 KB |
Output is correct |
5 |
Correct |
8 ms |
15572 KB |
Output is correct |
6 |
Correct |
8 ms |
15572 KB |
Output is correct |
7 |
Correct |
9 ms |
15492 KB |
Output is correct |
8 |
Correct |
8 ms |
15572 KB |
Output is correct |
9 |
Correct |
8 ms |
15616 KB |
Output is correct |
10 |
Correct |
291 ms |
34212 KB |
Output is correct |
11 |
Correct |
277 ms |
45828 KB |
Output is correct |
12 |
Correct |
70 ms |
21296 KB |
Output is correct |
13 |
Correct |
334 ms |
44172 KB |
Output is correct |
14 |
Correct |
185 ms |
48268 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
15572 KB |
Output is correct |
2 |
Correct |
8 ms |
15572 KB |
Output is correct |
3 |
Correct |
11 ms |
15572 KB |
Output is correct |
4 |
Correct |
11 ms |
15572 KB |
Output is correct |
5 |
Correct |
8 ms |
15572 KB |
Output is correct |
6 |
Correct |
8 ms |
15572 KB |
Output is correct |
7 |
Correct |
9 ms |
15492 KB |
Output is correct |
8 |
Correct |
8 ms |
15572 KB |
Output is correct |
9 |
Correct |
8 ms |
15616 KB |
Output is correct |
10 |
Correct |
8 ms |
15572 KB |
Output is correct |
11 |
Correct |
9 ms |
15492 KB |
Output is correct |
12 |
Correct |
8 ms |
15572 KB |
Output is correct |
13 |
Correct |
9 ms |
15568 KB |
Output is correct |
14 |
Correct |
10 ms |
15520 KB |
Output is correct |
15 |
Correct |
10 ms |
15608 KB |
Output is correct |
16 |
Correct |
10 ms |
15540 KB |
Output is correct |
17 |
Correct |
10 ms |
15572 KB |
Output is correct |
18 |
Correct |
9 ms |
15572 KB |
Output is correct |
19 |
Correct |
11 ms |
15572 KB |
Output is correct |
20 |
Correct |
10 ms |
15572 KB |
Output is correct |
21 |
Correct |
10 ms |
15492 KB |
Output is correct |
22 |
Correct |
8 ms |
15572 KB |
Output is correct |
23 |
Correct |
8 ms |
15572 KB |
Output is correct |
24 |
Correct |
9 ms |
15504 KB |
Output is correct |
25 |
Correct |
9 ms |
15572 KB |
Output is correct |
26 |
Correct |
10 ms |
15572 KB |
Output is correct |
27 |
Correct |
9 ms |
15700 KB |
Output is correct |
28 |
Correct |
12 ms |
15772 KB |
Output is correct |
29 |
Correct |
13 ms |
15692 KB |
Output is correct |
30 |
Correct |
11 ms |
15572 KB |
Output is correct |
31 |
Correct |
11 ms |
15572 KB |
Output is correct |
32 |
Correct |
11 ms |
15628 KB |
Output is correct |
33 |
Correct |
10 ms |
15564 KB |
Output is correct |
34 |
Correct |
10 ms |
15572 KB |
Output is correct |
35 |
Correct |
9 ms |
15572 KB |
Output is correct |
36 |
Correct |
9 ms |
15712 KB |
Output is correct |
37 |
Correct |
9 ms |
15700 KB |
Output is correct |
38 |
Correct |
10 ms |
15700 KB |
Output is correct |
39 |
Correct |
10 ms |
15748 KB |
Output is correct |
40 |
Correct |
13 ms |
15572 KB |
Output is correct |
41 |
Correct |
13 ms |
15700 KB |
Output is correct |
42 |
Correct |
291 ms |
34212 KB |
Output is correct |
43 |
Correct |
277 ms |
45828 KB |
Output is correct |
44 |
Correct |
70 ms |
21296 KB |
Output is correct |
45 |
Correct |
334 ms |
44172 KB |
Output is correct |
46 |
Correct |
185 ms |
48268 KB |
Output is correct |
47 |
Correct |
8 ms |
15572 KB |
Output is correct |
48 |
Correct |
9 ms |
15556 KB |
Output is correct |
49 |
Correct |
11 ms |
15572 KB |
Output is correct |
50 |
Correct |
166 ms |
45556 KB |
Output is correct |
51 |
Correct |
213 ms |
49304 KB |
Output is correct |
52 |
Correct |
270 ms |
43104 KB |
Output is correct |
53 |
Correct |
263 ms |
43124 KB |
Output is correct |
54 |
Correct |
311 ms |
43108 KB |
Output is correct |
55 |
Correct |
277 ms |
40908 KB |
Output is correct |
56 |
Correct |
342 ms |
51064 KB |
Output is correct |
57 |
Correct |
350 ms |
47832 KB |
Output is correct |
58 |
Correct |
297 ms |
58092 KB |
Output is correct |
59 |
Correct |
480 ms |
50192 KB |
Output is correct |
60 |
Correct |
351 ms |
49072 KB |
Output is correct |
61 |
Correct |
445 ms |
51276 KB |
Output is correct |
62 |
Correct |
1333 ms |
46556 KB |
Output is correct |
63 |
Correct |
221 ms |
45992 KB |
Output is correct |
64 |
Correct |
17 ms |
16088 KB |
Output is correct |
65 |
Correct |
16 ms |
16100 KB |
Output is correct |
66 |
Correct |
1289 ms |
46528 KB |
Output is correct |
67 |
Correct |
32 ms |
18836 KB |
Output is correct |
68 |
Correct |
43 ms |
20932 KB |
Output is correct |
69 |
Correct |
472 ms |
50116 KB |
Output is correct |
70 |
Correct |
66 ms |
26316 KB |
Output is correct |
71 |
Correct |
200 ms |
48808 KB |
Output is correct |
72 |
Correct |
449 ms |
50228 KB |
Output is correct |
73 |
Correct |
1160 ms |
46132 KB |
Output is correct |