# |
제출 시각 |
아이디 |
문제 |
언어 |
결과 |
실행 시간 |
메모리 |
623591 |
2022-08-06T03:47:52 Z |
Temmie |
열쇠 (IOI21_keys) |
C++17 |
|
2213 ms |
272164 KB |
#include <bits/stdc++.h>
struct Dsu {
std::vector <int> p;
std::vector <int> size;
Dsu(int s) {
p.resize(s);
std::iota(p.begin(), p.end(), 0);
size.resize(s, 1);
}
int find(int v) {
return v == p[v] ? v : (p[v] = find(p[v]));
}
void unite(int u, int v) {
if ((u = find(u)) == (v = find(v))) {
return;
}
p[u] = v;
//if (size[u] > size[v]) {
//p[v] = u;
//} else {
//p[u] = v;
//}
}
};
struct Edge {
int u, v, c;
};
int n, m;
std::vector <Edge> ed;
std::vector <std::vector <int>> g;
//std::vector <int> p;
Dsu dsu(0), can(0);
std::vector <int> r;
std::vector <bool> last;
bool go() {
//can = Dsu(n);
static std::vector <std::unordered_map <int, std::vector <int>>> mp(n);
static std::vector <std::unordered_set <int>> st(n);
bool did = false;
last.assign(n, false);
for (int i = 0; i < n; i++) {
if (dsu.find(i) != i) {
continue;
}
std::queue <std::pair <int, int>> q ; q.push ({ i, i });
while (q.size()) {
int v = q.front().first;
int p = q.front().second;
q.pop();
if (p != dsu.find(p)) {
continue;
}
if (dsu.find(v) != dsu.find(p)) {
did = true;
dsu.unite(p, v);
continue;
}
//if (can.find(v) == can.find(p)) {
//continue;
//}
//can.unite(v, p);
if (last[v]) {
continue;
}
last[v] = true;
for (int x : g[v]) {
int to = ed[x].u ^ ed[x].v ^ v;
if (st[p].count(ed[x].c)) {
q.push({ to, p });
} else {
mp[p][ed[x].c].push_back(to);
}
}
for (int x : mp[p][r[v]]) {
q.push({ x, p });
}
st[p].insert(r[v]);
mp[p][r[v]].clear();
}
}
//std::vector <std::vector <int>> in(n);
//for (int i = 0; i < n; i++) {
//in[dsu.find(i)].push_back(i);
//}
//std::vector <std::vector <int>> ed_of(n);
//bool did = false;
//for (int j = 0; j < n; j++) {
//int i = j;
//if (dsu.find(i) != i || p[i] != -1) {
//continue;
//}
//for (int v : in[i]) {
//for (int x : g[v]) {
//ed_of[ed[x].c].push_back(v ^ ed[x].v ^ ed[x].u);
//}
//}
//std::vector <int> eds;
//for (int x : in[i]) {
//for (int y : ed_of[r[x]]) {
//eds.push_back(y);
//}
//ed_of[r[x]].clear();
//}
//for (int x : eds) {
//if (dsu.find(x) == i) {
//continue;
//}
//did = true;
//if (tree.find(x) == tree.find(i)) {
//int to = dsu.find(x);
//while (i != to) {
//int new_to = dsu.find(p[to]);
//p[i] = p[to] = p[i];
//dsu.unite(to, i);
//i = dsu.find(i);
//to = new_to;
//}
//} else {
//p[i] = dsu.find(x);
//tree.unite(x, i);
//break;
//}
//}
//for (int v : in[i]) {
//for (int x : g[v]) {
//ed_of[ed[x].c].clear();
//}
//}
//}
//std::cerr << "did ?= " << did << std::endl;
return did;
}
std::vector <int> find_reachable(std::vector <int> _r, std::vector <int> u, std::vector <int> v, std::vector <int> c) {
r = _r;
n = r.size();
m = c.size();
ed.resize(m);
g.resize(n);
for (int i = 0; i < m; i++) {
g[u[i]].push_back(i);
g[v[i]].push_back(i);
ed[i] = { u[i], v[i], c[i] };
}
//p.resize(n, -1);
dsu = Dsu(n);
//tree = Dsu(n);
int cnt = 0;
while (go() && ++cnt < 135);// assert(++cnt < 100);
//for (int i = 0; i < n; i++) std::cerr << dsu.find(i) << " \n"[i + 1 == n];
std::vector <int> ans(n, 0);
for (int i = 0; i < n; i++) {
ans[dsu.find(i)] += last[i];// += p[dsu.find(i)] == -1;
}
int res = 1 << 30;
for (int x : ans) {
if (x) {
res = std::min(res, x);
}
}
std::vector <int> ret(n, 1);
for (int i = 0; i < n; i++) {
//if (ans[dsu.find(i)] == res) {
//ret[i] = 1;
//}
if(!last[i] || res != ans[dsu.find(i)]) {
ret[i] = 0;
}
}
return ret;
}
# |
결과 |
실행 시간 |
메모리 |
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 |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
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 |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
1 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 |
0 ms |
212 KB |
Output is correct |
14 |
Correct |
0 ms |
212 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
16 |
Correct |
0 ms |
212 KB |
Output is correct |
17 |
Correct |
0 ms |
212 KB |
Output is correct |
18 |
Correct |
0 ms |
340 KB |
Output is correct |
19 |
Correct |
0 ms |
212 KB |
Output is correct |
20 |
Correct |
0 ms |
212 KB |
Output is correct |
21 |
Correct |
0 ms |
340 KB |
Output is correct |
22 |
Correct |
1 ms |
340 KB |
Output is correct |
23 |
Correct |
1 ms |
340 KB |
Output is correct |
24 |
Correct |
1 ms |
340 KB |
Output is correct |
25 |
Correct |
1 ms |
340 KB |
Output is correct |
26 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
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 |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
1 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 |
0 ms |
212 KB |
Output is correct |
14 |
Correct |
0 ms |
212 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
16 |
Correct |
0 ms |
212 KB |
Output is correct |
17 |
Correct |
0 ms |
212 KB |
Output is correct |
18 |
Correct |
0 ms |
340 KB |
Output is correct |
19 |
Correct |
0 ms |
212 KB |
Output is correct |
20 |
Correct |
0 ms |
212 KB |
Output is correct |
21 |
Correct |
0 ms |
340 KB |
Output is correct |
22 |
Correct |
1 ms |
340 KB |
Output is correct |
23 |
Correct |
1 ms |
340 KB |
Output is correct |
24 |
Correct |
1 ms |
340 KB |
Output is correct |
25 |
Correct |
1 ms |
340 KB |
Output is correct |
26 |
Correct |
1 ms |
340 KB |
Output is correct |
27 |
Correct |
3 ms |
1492 KB |
Output is correct |
28 |
Correct |
3 ms |
1492 KB |
Output is correct |
29 |
Correct |
3 ms |
1492 KB |
Output is correct |
30 |
Correct |
2 ms |
852 KB |
Output is correct |
31 |
Correct |
1 ms |
852 KB |
Output is correct |
32 |
Correct |
1 ms |
468 KB |
Output is correct |
33 |
Correct |
2 ms |
852 KB |
Output is correct |
34 |
Correct |
2 ms |
852 KB |
Output is correct |
35 |
Correct |
2 ms |
724 KB |
Output is correct |
36 |
Correct |
2 ms |
1280 KB |
Output is correct |
37 |
Correct |
3 ms |
1492 KB |
Output is correct |
38 |
Correct |
3 ms |
1492 KB |
Output is correct |
39 |
Correct |
3 ms |
1748 KB |
Output is correct |
40 |
Correct |
2 ms |
980 KB |
Output is correct |
41 |
Correct |
3 ms |
1108 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
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 |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
434 ms |
97268 KB |
Output is correct |
11 |
Correct |
435 ms |
171896 KB |
Output is correct |
12 |
Correct |
102 ms |
37036 KB |
Output is correct |
13 |
Correct |
624 ms |
185540 KB |
Output is correct |
14 |
Correct |
299 ms |
170500 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
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 |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
1 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 |
0 ms |
212 KB |
Output is correct |
14 |
Correct |
0 ms |
212 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
16 |
Correct |
0 ms |
212 KB |
Output is correct |
17 |
Correct |
0 ms |
212 KB |
Output is correct |
18 |
Correct |
0 ms |
340 KB |
Output is correct |
19 |
Correct |
0 ms |
212 KB |
Output is correct |
20 |
Correct |
0 ms |
212 KB |
Output is correct |
21 |
Correct |
0 ms |
340 KB |
Output is correct |
22 |
Correct |
1 ms |
340 KB |
Output is correct |
23 |
Correct |
1 ms |
340 KB |
Output is correct |
24 |
Correct |
1 ms |
340 KB |
Output is correct |
25 |
Correct |
1 ms |
340 KB |
Output is correct |
26 |
Correct |
1 ms |
340 KB |
Output is correct |
27 |
Correct |
3 ms |
1492 KB |
Output is correct |
28 |
Correct |
3 ms |
1492 KB |
Output is correct |
29 |
Correct |
3 ms |
1492 KB |
Output is correct |
30 |
Correct |
2 ms |
852 KB |
Output is correct |
31 |
Correct |
1 ms |
852 KB |
Output is correct |
32 |
Correct |
1 ms |
468 KB |
Output is correct |
33 |
Correct |
2 ms |
852 KB |
Output is correct |
34 |
Correct |
2 ms |
852 KB |
Output is correct |
35 |
Correct |
2 ms |
724 KB |
Output is correct |
36 |
Correct |
2 ms |
1280 KB |
Output is correct |
37 |
Correct |
3 ms |
1492 KB |
Output is correct |
38 |
Correct |
3 ms |
1492 KB |
Output is correct |
39 |
Correct |
3 ms |
1748 KB |
Output is correct |
40 |
Correct |
2 ms |
980 KB |
Output is correct |
41 |
Correct |
3 ms |
1108 KB |
Output is correct |
42 |
Correct |
434 ms |
97268 KB |
Output is correct |
43 |
Correct |
435 ms |
171896 KB |
Output is correct |
44 |
Correct |
102 ms |
37036 KB |
Output is correct |
45 |
Correct |
624 ms |
185540 KB |
Output is correct |
46 |
Correct |
299 ms |
170500 KB |
Output is correct |
47 |
Correct |
0 ms |
212 KB |
Output is correct |
48 |
Correct |
0 ms |
212 KB |
Output is correct |
49 |
Correct |
0 ms |
212 KB |
Output is correct |
50 |
Correct |
295 ms |
168216 KB |
Output is correct |
51 |
Correct |
333 ms |
170480 KB |
Output is correct |
52 |
Correct |
354 ms |
131828 KB |
Output is correct |
53 |
Correct |
354 ms |
131816 KB |
Output is correct |
54 |
Correct |
353 ms |
131788 KB |
Output is correct |
55 |
Correct |
409 ms |
109048 KB |
Output is correct |
56 |
Correct |
527 ms |
186888 KB |
Output is correct |
57 |
Correct |
502 ms |
183488 KB |
Output is correct |
58 |
Correct |
464 ms |
194420 KB |
Output is correct |
59 |
Correct |
689 ms |
170360 KB |
Output is correct |
60 |
Correct |
567 ms |
166016 KB |
Output is correct |
61 |
Correct |
599 ms |
168908 KB |
Output is correct |
62 |
Correct |
2213 ms |
265872 KB |
Output is correct |
63 |
Correct |
418 ms |
155416 KB |
Output is correct |
64 |
Correct |
6 ms |
3284 KB |
Output is correct |
65 |
Correct |
6 ms |
3276 KB |
Output is correct |
66 |
Correct |
2163 ms |
272164 KB |
Output is correct |
67 |
Correct |
35 ms |
17868 KB |
Output is correct |
68 |
Correct |
53 ms |
29604 KB |
Output is correct |
69 |
Correct |
703 ms |
177296 KB |
Output is correct |
70 |
Correct |
106 ms |
59080 KB |
Output is correct |
71 |
Correct |
313 ms |
176616 KB |
Output is correct |
72 |
Correct |
721 ms |
177448 KB |
Output is correct |
73 |
Correct |
2186 ms |
272120 KB |
Output is correct |