# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
497116 |
2021-12-22T12:52:55 Z |
NachoLibre |
Keys (IOI21_keys) |
C++17 |
|
1254 ms |
257496 KB |
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define vint vector<int>
using namespace std;
#ifndef wambule
// #include ".h"
#else
#endif
const int N = 300005;
struct vert {
vert() {
next = -1;
size = 1;
}
set<pair<int, int> > locked;
set<int> keys;
set<int> unlocked;
set<int> vertices;
int next, size;
void add_key(int key) {
if(keys.find(key) != keys.end()) return;
for(;;) {
auto it = locked.lower_bound({key, 0});
if(it == locked.end() || (*it).first != key) break;
unlocked.insert((*it).second);
locked.erase(it);
}
keys.insert(key);
}
void add_edge(int x, int y) {
if(keys.find(y) != keys.end()) {
unlocked.insert(x);
} else {
locked.insert({y, x});
}
}
};
int n, m;
int up[N], up2[N];
vert vx[N];
queue<int> evolution;
vector<int> done;
int P(int x) {
return (up[x] < 0 ? x : up[x] = P(up[x]));
}
int P2(int x) {
return (up2[x] < 0 ? x : up2[x] = P2(up2[x]));
}
int Sz(int x) {
return -up[P(x)];
}
void merge(int x, int y) {
if(vx[x].size < vx[y].size) {
swap(vx[x], vx[y]);
}
up2[P2(y)] = P2(x);
vx[x].size += vx[y].size;
for(auto key : vx[y].keys) {
vx[x].add_key(key);
}
for(auto edge : vx[y].locked) {
vx[x].add_edge(edge.second, edge.first);
}
for(auto vertex : vx[y].unlocked) {
vx[x].unlocked.insert(vertex);
}
for(auto vertex : vx[y].vertices) {
vx[x].vertices.insert(vertex);
}
}
void activate(int x) {
x = P2(x);
while(vx[x].unlocked.size() && P2(*vx[x].unlocked.begin()) == x) {
vx[x].unlocked.erase(vx[x].unlocked.begin());
}
if(!vx[x].unlocked.size()) {
done.push_back(x);
return;
}
int y = P2(*vx[x].unlocked.begin());
if(P(x) != P(y)) {
up[P(x)] = P(y);
vx[x].next = y;
} else {
for(;;) {
int z = P2(vx[y].next);
merge(x, y);
y = z;
if(y == x) break;
}
evolution.push(x);
}
}
vint find_reachable(vint _R, vint _U, vint _V, vint _C) {
n = _R.size();
m = _U.size();
vint ans(n, 0);
for(int i = 0; i < n; ++i) {
up[i] = up2[i] = -1;
vx[i].vertices.insert(i);
vx[i].add_key(_R[i]);
}
for(int i = 0; i < m; ++i) {
int x = _U[i];
int y = _V[i];
int z = _C[i];
// cout << x << " " << y << " " << z << endl;
vx[x].add_edge(y, z);
vx[y].add_edge(x, z);
}
for(int i = 0; i < n; ++i) {
evolution.push(i);
}
while(evolution.size()) {
activate(evolution.front());
evolution.pop();
}
int fp = 1e9;
for(int x : done) {
fp = min(fp, vx[x].size);
}
for(int x : done) {
if(vx[x].size == fp) {
for(int y : vx[x].vertices) {
ans[y] = 1;
}
}
}
return ans;
}
#ifdef wambule
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
// vint v = find_reachable({0, 1, 1, 2}, {0, 0, 1, 1, 3}, {1, 2, 2, 3, 1}, {0, 0, 1, 0, 2});
// for(int i = 0; i < sz(v); ++i) {
// if(v[i]) cout << i << " ";
// }
// cout << endl;
vint v = find_reachable({0, 1, 1, 2, 2, 1, 2},
{0, 0, 1, 1, 2, 3, 3, 4, 4, 5},
{1, 2, 2, 3, 3, 4, 5, 5, 6, 6},
{0, 0, 1, 0, 0, 1, 2, 0, 2, 1});
for(int i = 0; i < sz(v); ++i) {
if(v[i]) cout << i << " ";
}
cout << endl;
return 0;
}
#endif
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
26 ms |
58936 KB |
Output is correct |
2 |
Correct |
26 ms |
58956 KB |
Output is correct |
3 |
Correct |
27 ms |
58948 KB |
Output is correct |
4 |
Correct |
32 ms |
58964 KB |
Output is correct |
5 |
Correct |
31 ms |
59116 KB |
Output is correct |
6 |
Correct |
29 ms |
58924 KB |
Output is correct |
7 |
Correct |
32 ms |
58976 KB |
Output is correct |
8 |
Correct |
27 ms |
59012 KB |
Output is correct |
9 |
Correct |
27 ms |
58948 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
26 ms |
58936 KB |
Output is correct |
2 |
Correct |
26 ms |
58956 KB |
Output is correct |
3 |
Correct |
27 ms |
58948 KB |
Output is correct |
4 |
Correct |
32 ms |
58964 KB |
Output is correct |
5 |
Correct |
31 ms |
59116 KB |
Output is correct |
6 |
Correct |
29 ms |
58924 KB |
Output is correct |
7 |
Correct |
32 ms |
58976 KB |
Output is correct |
8 |
Correct |
27 ms |
59012 KB |
Output is correct |
9 |
Correct |
27 ms |
58948 KB |
Output is correct |
10 |
Correct |
26 ms |
59020 KB |
Output is correct |
11 |
Correct |
27 ms |
58956 KB |
Output is correct |
12 |
Correct |
26 ms |
59012 KB |
Output is correct |
13 |
Correct |
34 ms |
58884 KB |
Output is correct |
14 |
Correct |
30 ms |
58956 KB |
Output is correct |
15 |
Correct |
29 ms |
59064 KB |
Output is correct |
16 |
Correct |
28 ms |
58924 KB |
Output is correct |
17 |
Correct |
30 ms |
59012 KB |
Output is correct |
18 |
Correct |
30 ms |
58980 KB |
Output is correct |
19 |
Correct |
27 ms |
58952 KB |
Output is correct |
20 |
Correct |
27 ms |
58924 KB |
Output is correct |
21 |
Correct |
27 ms |
59092 KB |
Output is correct |
22 |
Correct |
27 ms |
59032 KB |
Output is correct |
23 |
Correct |
28 ms |
58940 KB |
Output is correct |
24 |
Correct |
27 ms |
59016 KB |
Output is correct |
25 |
Correct |
27 ms |
58952 KB |
Output is correct |
26 |
Correct |
33 ms |
58972 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
26 ms |
58936 KB |
Output is correct |
2 |
Correct |
26 ms |
58956 KB |
Output is correct |
3 |
Correct |
27 ms |
58948 KB |
Output is correct |
4 |
Correct |
32 ms |
58964 KB |
Output is correct |
5 |
Correct |
31 ms |
59116 KB |
Output is correct |
6 |
Correct |
29 ms |
58924 KB |
Output is correct |
7 |
Correct |
32 ms |
58976 KB |
Output is correct |
8 |
Correct |
27 ms |
59012 KB |
Output is correct |
9 |
Correct |
27 ms |
58948 KB |
Output is correct |
10 |
Correct |
26 ms |
59020 KB |
Output is correct |
11 |
Correct |
27 ms |
58956 KB |
Output is correct |
12 |
Correct |
26 ms |
59012 KB |
Output is correct |
13 |
Correct |
34 ms |
58884 KB |
Output is correct |
14 |
Correct |
30 ms |
58956 KB |
Output is correct |
15 |
Correct |
29 ms |
59064 KB |
Output is correct |
16 |
Correct |
28 ms |
58924 KB |
Output is correct |
17 |
Correct |
30 ms |
59012 KB |
Output is correct |
18 |
Correct |
30 ms |
58980 KB |
Output is correct |
19 |
Correct |
27 ms |
58952 KB |
Output is correct |
20 |
Correct |
27 ms |
58924 KB |
Output is correct |
21 |
Correct |
27 ms |
59092 KB |
Output is correct |
22 |
Correct |
27 ms |
59032 KB |
Output is correct |
23 |
Correct |
28 ms |
58940 KB |
Output is correct |
24 |
Correct |
27 ms |
59016 KB |
Output is correct |
25 |
Correct |
27 ms |
58952 KB |
Output is correct |
26 |
Correct |
33 ms |
58972 KB |
Output is correct |
27 |
Correct |
29 ms |
59452 KB |
Output is correct |
28 |
Correct |
31 ms |
59420 KB |
Output is correct |
29 |
Correct |
32 ms |
59452 KB |
Output is correct |
30 |
Correct |
30 ms |
59268 KB |
Output is correct |
31 |
Correct |
29 ms |
59192 KB |
Output is correct |
32 |
Correct |
27 ms |
59016 KB |
Output is correct |
33 |
Correct |
28 ms |
59288 KB |
Output is correct |
34 |
Correct |
29 ms |
59264 KB |
Output is correct |
35 |
Correct |
30 ms |
59340 KB |
Output is correct |
36 |
Correct |
32 ms |
59364 KB |
Output is correct |
37 |
Correct |
30 ms |
59656 KB |
Output is correct |
38 |
Correct |
31 ms |
59760 KB |
Output is correct |
39 |
Correct |
30 ms |
59724 KB |
Output is correct |
40 |
Correct |
29 ms |
59312 KB |
Output is correct |
41 |
Correct |
29 ms |
59428 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
26 ms |
58936 KB |
Output is correct |
2 |
Correct |
26 ms |
58956 KB |
Output is correct |
3 |
Correct |
27 ms |
58948 KB |
Output is correct |
4 |
Correct |
32 ms |
58964 KB |
Output is correct |
5 |
Correct |
31 ms |
59116 KB |
Output is correct |
6 |
Correct |
29 ms |
58924 KB |
Output is correct |
7 |
Correct |
32 ms |
58976 KB |
Output is correct |
8 |
Correct |
27 ms |
59012 KB |
Output is correct |
9 |
Correct |
27 ms |
58948 KB |
Output is correct |
10 |
Correct |
574 ms |
118504 KB |
Output is correct |
11 |
Correct |
751 ms |
146428 KB |
Output is correct |
12 |
Correct |
104 ms |
77396 KB |
Output is correct |
13 |
Correct |
514 ms |
149752 KB |
Output is correct |
14 |
Correct |
403 ms |
161476 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
26 ms |
58936 KB |
Output is correct |
2 |
Correct |
26 ms |
58956 KB |
Output is correct |
3 |
Correct |
27 ms |
58948 KB |
Output is correct |
4 |
Correct |
32 ms |
58964 KB |
Output is correct |
5 |
Correct |
31 ms |
59116 KB |
Output is correct |
6 |
Correct |
29 ms |
58924 KB |
Output is correct |
7 |
Correct |
32 ms |
58976 KB |
Output is correct |
8 |
Correct |
27 ms |
59012 KB |
Output is correct |
9 |
Correct |
27 ms |
58948 KB |
Output is correct |
10 |
Correct |
26 ms |
59020 KB |
Output is correct |
11 |
Correct |
27 ms |
58956 KB |
Output is correct |
12 |
Correct |
26 ms |
59012 KB |
Output is correct |
13 |
Correct |
34 ms |
58884 KB |
Output is correct |
14 |
Correct |
30 ms |
58956 KB |
Output is correct |
15 |
Correct |
29 ms |
59064 KB |
Output is correct |
16 |
Correct |
28 ms |
58924 KB |
Output is correct |
17 |
Correct |
30 ms |
59012 KB |
Output is correct |
18 |
Correct |
30 ms |
58980 KB |
Output is correct |
19 |
Correct |
27 ms |
58952 KB |
Output is correct |
20 |
Correct |
27 ms |
58924 KB |
Output is correct |
21 |
Correct |
27 ms |
59092 KB |
Output is correct |
22 |
Correct |
27 ms |
59032 KB |
Output is correct |
23 |
Correct |
28 ms |
58940 KB |
Output is correct |
24 |
Correct |
27 ms |
59016 KB |
Output is correct |
25 |
Correct |
27 ms |
58952 KB |
Output is correct |
26 |
Correct |
33 ms |
58972 KB |
Output is correct |
27 |
Correct |
29 ms |
59452 KB |
Output is correct |
28 |
Correct |
31 ms |
59420 KB |
Output is correct |
29 |
Correct |
32 ms |
59452 KB |
Output is correct |
30 |
Correct |
30 ms |
59268 KB |
Output is correct |
31 |
Correct |
29 ms |
59192 KB |
Output is correct |
32 |
Correct |
27 ms |
59016 KB |
Output is correct |
33 |
Correct |
28 ms |
59288 KB |
Output is correct |
34 |
Correct |
29 ms |
59264 KB |
Output is correct |
35 |
Correct |
30 ms |
59340 KB |
Output is correct |
36 |
Correct |
32 ms |
59364 KB |
Output is correct |
37 |
Correct |
30 ms |
59656 KB |
Output is correct |
38 |
Correct |
31 ms |
59760 KB |
Output is correct |
39 |
Correct |
30 ms |
59724 KB |
Output is correct |
40 |
Correct |
29 ms |
59312 KB |
Output is correct |
41 |
Correct |
29 ms |
59428 KB |
Output is correct |
42 |
Correct |
574 ms |
118504 KB |
Output is correct |
43 |
Correct |
751 ms |
146428 KB |
Output is correct |
44 |
Correct |
104 ms |
77396 KB |
Output is correct |
45 |
Correct |
514 ms |
149752 KB |
Output is correct |
46 |
Correct |
403 ms |
161476 KB |
Output is correct |
47 |
Correct |
27 ms |
58996 KB |
Output is correct |
48 |
Correct |
28 ms |
58984 KB |
Output is correct |
49 |
Correct |
28 ms |
58900 KB |
Output is correct |
50 |
Correct |
380 ms |
146756 KB |
Output is correct |
51 |
Correct |
369 ms |
149964 KB |
Output is correct |
52 |
Correct |
300 ms |
111668 KB |
Output is correct |
53 |
Correct |
294 ms |
111680 KB |
Output is correct |
54 |
Correct |
313 ms |
111760 KB |
Output is correct |
55 |
Correct |
650 ms |
121040 KB |
Output is correct |
56 |
Correct |
550 ms |
138444 KB |
Output is correct |
57 |
Correct |
581 ms |
139648 KB |
Output is correct |
58 |
Correct |
521 ms |
137364 KB |
Output is correct |
59 |
Correct |
1170 ms |
147392 KB |
Output is correct |
60 |
Correct |
1213 ms |
157708 KB |
Output is correct |
61 |
Correct |
1254 ms |
157948 KB |
Output is correct |
62 |
Correct |
1116 ms |
257496 KB |
Output is correct |
63 |
Correct |
271 ms |
143080 KB |
Output is correct |
64 |
Correct |
39 ms |
60668 KB |
Output is correct |
65 |
Correct |
35 ms |
60616 KB |
Output is correct |
66 |
Correct |
1188 ms |
257076 KB |
Output is correct |
67 |
Correct |
69 ms |
69260 KB |
Output is correct |
68 |
Correct |
95 ms |
76108 KB |
Output is correct |
69 |
Correct |
1207 ms |
147264 KB |
Output is correct |
70 |
Correct |
169 ms |
93324 KB |
Output is correct |
71 |
Correct |
470 ms |
162476 KB |
Output is correct |
72 |
Correct |
1222 ms |
147360 KB |
Output is correct |
73 |
Correct |
1117 ms |
257224 KB |
Output is correct |