# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
597886 |
2022-07-17T04:07:28 Z |
KoD |
Keys (IOI21_keys) |
C++17 |
|
1082 ms |
150000 KB |
#include "keys.h"
#include <bits/stdc++.h>
using namespace std;
struct UnionFind {
vector<int> data;
explicit UnionFind(const int n) : data(n, -1) {}
int find(const int x) {
return data[x] < 0 ? x : data[x] = find(data[x]);
}
int merge(int x, int y) {
x = find(x);
y = find(y);
if (x != y) {
if (data[x] > data[y]) {
swap(x, y);
}
data[x] += data[y];
data[y] = x;
}
return x;
}
};
vector<int> find_reachable(vector<int> R, vector<int> U, vector<int> V, vector<int> C) {
const int N = (int)size(R);
const int M = (int)size(C);
struct Data {
vector<int> open;
set<int> keys;
map<int, vector<int>> locked;
void add_edge(const int u, const int k) {
if (keys.find(k) != end(keys)) {
open.push_back(u);
} else {
locked[k].push_back(u);
}
}
void add_key(const int x) {
if (const auto itr = locked.find(x); itr != end(locked)) {
for (const int u : itr->second) {
open.push_back(u);
}
locked.erase(itr);
}
keys.insert(x);
}
};
UnionFind cycle(N);
vector<Data> data(N);
vector<int> status(N), toward(N), reach(N, N + 1);
for (int i = 0; i < N; ++i) {
data[i].keys.insert(R[i]);
}
for (int i = 0; i < M; ++i) {
data[U[i]].add_edge(V[i], C[i]);
data[V[i]].add_edge(U[i], C[i]);
}
for (int see = 0; see < N; ++see) {
if (status[see] == 1) {
continue;
}
vector<int> list;
for (int u = see; status[u] != 1;) {
if (status[u] == 0) {
status[u] = -1;
list.push_back(u);
}
if (data[u].open.empty()) {
vector<int> same;
for (const int x : list) {
if (cycle.find(x) == u) {
same.push_back(x);
}
}
const int n = (int)size(same);
for (const int x : same) {
reach[x] = n;
}
break;
}
toward[u] = cycle.find(data[u].open.back());
data[u].open.pop_back();
if (status[toward[u]] == -1) {
int v = u;
while (true) {
v = cycle.find(toward[v]);
if (v == u) {
break;
}
const int r = cycle.merge(u, v);
const auto& move = data[r == u ? v : u];
u = r;
for (const int x : move.open) {
data[u].open.push_back(x);
}
for (const int x : move.keys) {
data[u].add_key(x);
}
for (const auto& [k, vec] : move.locked) {
for (const int x : vec) {
data[u].add_edge(x, k);
}
}
}
} else {
u = toward[u];
}
}
for (const int v : list) {
// std::cerr << v << ' ';
status[v] = 1;
}
// std::cerr << std::endl;
}
const int min = *min_element(begin(reach), end(reach));
vector<int> ret(N);
for (int i = 0; i < N; ++i) {
ret[i] = min == reach[i];
}
return ret;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
212 KB |
Output is correct |
14 |
Correct |
0 ms |
212 KB |
Output is correct |
15 |
Correct |
1 ms |
296 KB |
Output is correct |
16 |
Correct |
1 ms |
212 KB |
Output is correct |
17 |
Correct |
0 ms |
212 KB |
Output is correct |
18 |
Correct |
1 ms |
212 KB |
Output is correct |
19 |
Correct |
0 ms |
300 KB |
Output is correct |
20 |
Correct |
0 ms |
212 KB |
Output is correct |
21 |
Correct |
1 ms |
340 KB |
Output is correct |
22 |
Correct |
1 ms |
212 KB |
Output is correct |
23 |
Correct |
1 ms |
340 KB |
Output is correct |
24 |
Correct |
1 ms |
300 KB |
Output is correct |
25 |
Correct |
1 ms |
300 KB |
Output is correct |
26 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
212 KB |
Output is correct |
14 |
Correct |
0 ms |
212 KB |
Output is correct |
15 |
Correct |
1 ms |
296 KB |
Output is correct |
16 |
Correct |
1 ms |
212 KB |
Output is correct |
17 |
Correct |
0 ms |
212 KB |
Output is correct |
18 |
Correct |
1 ms |
212 KB |
Output is correct |
19 |
Correct |
0 ms |
300 KB |
Output is correct |
20 |
Correct |
0 ms |
212 KB |
Output is correct |
21 |
Correct |
1 ms |
340 KB |
Output is correct |
22 |
Correct |
1 ms |
212 KB |
Output is correct |
23 |
Correct |
1 ms |
340 KB |
Output is correct |
24 |
Correct |
1 ms |
300 KB |
Output is correct |
25 |
Correct |
1 ms |
300 KB |
Output is correct |
26 |
Correct |
1 ms |
340 KB |
Output is correct |
27 |
Correct |
2 ms |
1108 KB |
Output is correct |
28 |
Correct |
2 ms |
1108 KB |
Output is correct |
29 |
Correct |
3 ms |
1080 KB |
Output is correct |
30 |
Correct |
1 ms |
596 KB |
Output is correct |
31 |
Correct |
1 ms |
596 KB |
Output is correct |
32 |
Correct |
1 ms |
340 KB |
Output is correct |
33 |
Correct |
2 ms |
572 KB |
Output is correct |
34 |
Correct |
1 ms |
596 KB |
Output is correct |
35 |
Correct |
2 ms |
596 KB |
Output is correct |
36 |
Correct |
2 ms |
980 KB |
Output is correct |
37 |
Correct |
2 ms |
980 KB |
Output is correct |
38 |
Correct |
3 ms |
1048 KB |
Output is correct |
39 |
Correct |
3 ms |
1132 KB |
Output is correct |
40 |
Correct |
2 ms |
724 KB |
Output is correct |
41 |
Correct |
2 ms |
980 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
570 ms |
78808 KB |
Output is correct |
11 |
Correct |
370 ms |
82276 KB |
Output is correct |
12 |
Correct |
93 ms |
22572 KB |
Output is correct |
13 |
Correct |
515 ms |
107424 KB |
Output is correct |
14 |
Correct |
182 ms |
83952 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
212 KB |
Output is correct |
14 |
Correct |
0 ms |
212 KB |
Output is correct |
15 |
Correct |
1 ms |
296 KB |
Output is correct |
16 |
Correct |
1 ms |
212 KB |
Output is correct |
17 |
Correct |
0 ms |
212 KB |
Output is correct |
18 |
Correct |
1 ms |
212 KB |
Output is correct |
19 |
Correct |
0 ms |
300 KB |
Output is correct |
20 |
Correct |
0 ms |
212 KB |
Output is correct |
21 |
Correct |
1 ms |
340 KB |
Output is correct |
22 |
Correct |
1 ms |
212 KB |
Output is correct |
23 |
Correct |
1 ms |
340 KB |
Output is correct |
24 |
Correct |
1 ms |
300 KB |
Output is correct |
25 |
Correct |
1 ms |
300 KB |
Output is correct |
26 |
Correct |
1 ms |
340 KB |
Output is correct |
27 |
Correct |
2 ms |
1108 KB |
Output is correct |
28 |
Correct |
2 ms |
1108 KB |
Output is correct |
29 |
Correct |
3 ms |
1080 KB |
Output is correct |
30 |
Correct |
1 ms |
596 KB |
Output is correct |
31 |
Correct |
1 ms |
596 KB |
Output is correct |
32 |
Correct |
1 ms |
340 KB |
Output is correct |
33 |
Correct |
2 ms |
572 KB |
Output is correct |
34 |
Correct |
1 ms |
596 KB |
Output is correct |
35 |
Correct |
2 ms |
596 KB |
Output is correct |
36 |
Correct |
2 ms |
980 KB |
Output is correct |
37 |
Correct |
2 ms |
980 KB |
Output is correct |
38 |
Correct |
3 ms |
1048 KB |
Output is correct |
39 |
Correct |
3 ms |
1132 KB |
Output is correct |
40 |
Correct |
2 ms |
724 KB |
Output is correct |
41 |
Correct |
2 ms |
980 KB |
Output is correct |
42 |
Correct |
570 ms |
78808 KB |
Output is correct |
43 |
Correct |
370 ms |
82276 KB |
Output is correct |
44 |
Correct |
93 ms |
22572 KB |
Output is correct |
45 |
Correct |
515 ms |
107424 KB |
Output is correct |
46 |
Correct |
182 ms |
83952 KB |
Output is correct |
47 |
Correct |
1 ms |
212 KB |
Output is correct |
48 |
Correct |
1 ms |
308 KB |
Output is correct |
49 |
Correct |
0 ms |
212 KB |
Output is correct |
50 |
Correct |
176 ms |
82892 KB |
Output is correct |
51 |
Correct |
203 ms |
85536 KB |
Output is correct |
52 |
Correct |
388 ms |
84416 KB |
Output is correct |
53 |
Correct |
393 ms |
84444 KB |
Output is correct |
54 |
Correct |
396 ms |
84436 KB |
Output is correct |
55 |
Correct |
726 ms |
92804 KB |
Output is correct |
56 |
Correct |
465 ms |
110240 KB |
Output is correct |
57 |
Correct |
384 ms |
106944 KB |
Output is correct |
58 |
Correct |
679 ms |
114952 KB |
Output is correct |
59 |
Correct |
1082 ms |
119968 KB |
Output is correct |
60 |
Correct |
535 ms |
94748 KB |
Output is correct |
61 |
Correct |
792 ms |
107156 KB |
Output is correct |
62 |
Correct |
855 ms |
149968 KB |
Output is correct |
63 |
Correct |
263 ms |
97996 KB |
Output is correct |
64 |
Correct |
4 ms |
1620 KB |
Output is correct |
65 |
Correct |
4 ms |
1716 KB |
Output is correct |
66 |
Correct |
847 ms |
149956 KB |
Output is correct |
67 |
Correct |
19 ms |
8660 KB |
Output is correct |
68 |
Correct |
31 ms |
14216 KB |
Output is correct |
69 |
Correct |
1055 ms |
119964 KB |
Output is correct |
70 |
Correct |
63 ms |
27956 KB |
Output is correct |
71 |
Correct |
198 ms |
84580 KB |
Output is correct |
72 |
Correct |
1076 ms |
119772 KB |
Output is correct |
73 |
Correct |
853 ms |
150000 KB |
Output is correct |