#include <bits/stdc++.h>
using namespace std;
namespace {
struct disjoint_set {
vector<int> par, siz;
void init(int n) {
par.assign(n, -1);
siz.assign(n, 1);
}
int find(int u) {
if (par[u] < 0) return u;
return par[u] = find(par[u]);
}
bool unite(int u, int v) {
u = find(u); v = find(v);
if (u == v) return false;
par[v] = u; siz[u] += siz[v];
return true;
}
bool same(int u, int v) {
return find(u) == find(v);
}
} roots, forests;
vector<set<pair<int, int>>> locks;
vector<vector<int>> unlocks;
vector<set<int>> keys;
vector<int> nxt, vis;
void unite(int u, int v) {
if (size(unlocks[u]) < size(unlocks[v]))
swap(unlocks[u], unlocks[v]);
for (int w : unlocks[v])
unlocks[u].push_back(w);
if (size(locks[u]) + size(keys[u])
< size(locks[v]) + size(keys[v])) {
swap(locks[u], locks[v]);
swap(keys[u], keys[v]);
}
for (auto edge : locks[v]) {
if (keys[u].count(edge.first))
unlocks[u].push_back(edge.second);
else locks[u].insert(edge);
}
for (auto key : keys[v]) {
auto iter = locks[u].
lower_bound(make_pair(key, -1));
while (iter != locks[u].end()
&& iter->first == key) {
unlocks[u].push_back(iter->second);
iter = locks[u].erase(iter);
}
keys[u].insert(key);
}
}
void dfs(int u) {
vis[u] = 2;
if (!vis[nxt[u]]) dfs(nxt[u]);
else if (vis[nxt[u]] == 2) {
int v = nxt[u];
while (u != v) {
roots.unite(u, v);
unite(u, v); v = nxt[v];
}
while (unlocks[u].size()) {
int v = unlocks[u].back();
unlocks[u].pop_back();
if (forests.unite(v, u)) {
nxt[u] = v; break;
}
while (!roots.same(u, v)) {
unite(u, v = roots.find(v));
roots.unite(nxt[v], v);
}
}
}
vis[u] = 1;
}
}
vector<int> find_reachable(vector<int> r,
vector<int> u, vector<int> v, vector<int> c) {
int n = r.size(); locks.resize(n);
unlocks.resize(n); keys.resize(n);
nxt.resize(n); vis.resize(n);
roots.init(n); forests.init(n);
for (int i = 0; i < u.size(); i++) {
locks[u[i]].emplace(c[i], v[i]);
locks[v[i]].emplace(c[i], u[i]);
}
bool flag = false;
for (int i = 0; i < n; i++) {
keys[i].insert(r[i]); nxt[i] = -1;
auto iter = locks[i].
lower_bound(make_pair(r[i], -1));
while (iter != locks[i].end()
&& iter->first == r[i]) {
unlocks[i].push_back(iter->second);
nxt[i] = iter->second;
iter = locks[i].erase(iter);
}
if (nxt[i] < 0) flag = true;
else forests.unite(nxt[i], i);
}
if (flag) {
for (int i = 0; i < n; i++)
if (nxt[i] < 0) nxt[i] = 1;
else nxt[i] = 0;
return nxt;
}
for (int i = 0; i < n; i++)
if (!vis[i]) dfs(i);
int res = n;
for (int i = 0; i < n; i++)
if (forests.par[i] < 0) {
int j = roots.find(i);
res = min(res, roots.siz[j]);
}
vis.assign(n, 0);
for (int i = 0; i < n; i++) {
int j = forests.find(i);
if (roots.same(i, j)) {
j = roots.find(i);
vis[i] = res == roots.siz[j];
}
}
return vis;
}
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:94:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
94 | for (int i = 0; i < u.size(); i++) {
| ~~^~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
284 KB |
Output is correct |
8 |
Correct |
1 ms |
332 KB |
Output is correct |
9 |
Correct |
1 ms |
332 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
284 KB |
Output is correct |
8 |
Correct |
1 ms |
332 KB |
Output is correct |
9 |
Correct |
1 ms |
332 KB |
Output is correct |
10 |
Correct |
1 ms |
332 KB |
Output is correct |
11 |
Correct |
1 ms |
332 KB |
Output is correct |
12 |
Correct |
1 ms |
332 KB |
Output is correct |
13 |
Correct |
1 ms |
204 KB |
Output is correct |
14 |
Correct |
1 ms |
204 KB |
Output is correct |
15 |
Correct |
1 ms |
332 KB |
Output is correct |
16 |
Correct |
1 ms |
204 KB |
Output is correct |
17 |
Correct |
1 ms |
204 KB |
Output is correct |
18 |
Correct |
1 ms |
204 KB |
Output is correct |
19 |
Correct |
1 ms |
204 KB |
Output is correct |
20 |
Correct |
1 ms |
204 KB |
Output is correct |
21 |
Correct |
1 ms |
332 KB |
Output is correct |
22 |
Correct |
1 ms |
204 KB |
Output is correct |
23 |
Correct |
1 ms |
332 KB |
Output is correct |
24 |
Correct |
1 ms |
332 KB |
Output is correct |
25 |
Correct |
1 ms |
332 KB |
Output is correct |
26 |
Correct |
1 ms |
332 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
284 KB |
Output is correct |
8 |
Correct |
1 ms |
332 KB |
Output is correct |
9 |
Correct |
1 ms |
332 KB |
Output is correct |
10 |
Correct |
1 ms |
332 KB |
Output is correct |
11 |
Correct |
1 ms |
332 KB |
Output is correct |
12 |
Correct |
1 ms |
332 KB |
Output is correct |
13 |
Correct |
1 ms |
204 KB |
Output is correct |
14 |
Correct |
1 ms |
204 KB |
Output is correct |
15 |
Correct |
1 ms |
332 KB |
Output is correct |
16 |
Correct |
1 ms |
204 KB |
Output is correct |
17 |
Correct |
1 ms |
204 KB |
Output is correct |
18 |
Correct |
1 ms |
204 KB |
Output is correct |
19 |
Correct |
1 ms |
204 KB |
Output is correct |
20 |
Correct |
1 ms |
204 KB |
Output is correct |
21 |
Correct |
1 ms |
332 KB |
Output is correct |
22 |
Correct |
1 ms |
204 KB |
Output is correct |
23 |
Correct |
1 ms |
332 KB |
Output is correct |
24 |
Correct |
1 ms |
332 KB |
Output is correct |
25 |
Correct |
1 ms |
332 KB |
Output is correct |
26 |
Correct |
1 ms |
332 KB |
Output is correct |
27 |
Correct |
3 ms |
844 KB |
Output is correct |
28 |
Correct |
2 ms |
844 KB |
Output is correct |
29 |
Correct |
2 ms |
844 KB |
Output is correct |
30 |
Correct |
2 ms |
588 KB |
Output is correct |
31 |
Correct |
2 ms |
460 KB |
Output is correct |
32 |
Correct |
1 ms |
332 KB |
Output is correct |
33 |
Correct |
3 ms |
460 KB |
Output is correct |
34 |
Correct |
2 ms |
716 KB |
Output is correct |
35 |
Correct |
1 ms |
460 KB |
Output is correct |
36 |
Correct |
2 ms |
716 KB |
Output is correct |
37 |
Correct |
2 ms |
716 KB |
Output is correct |
38 |
Correct |
2 ms |
844 KB |
Output is correct |
39 |
Correct |
3 ms |
844 KB |
Output is correct |
40 |
Correct |
2 ms |
588 KB |
Output is correct |
41 |
Correct |
4 ms |
716 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
284 KB |
Output is correct |
8 |
Correct |
1 ms |
332 KB |
Output is correct |
9 |
Correct |
1 ms |
332 KB |
Output is correct |
10 |
Correct |
548 ms |
53836 KB |
Output is correct |
11 |
Correct |
756 ms |
91456 KB |
Output is correct |
12 |
Correct |
128 ms |
18000 KB |
Output is correct |
13 |
Correct |
674 ms |
89396 KB |
Output is correct |
14 |
Correct |
317 ms |
125500 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
284 KB |
Output is correct |
8 |
Correct |
1 ms |
332 KB |
Output is correct |
9 |
Correct |
1 ms |
332 KB |
Output is correct |
10 |
Correct |
1 ms |
332 KB |
Output is correct |
11 |
Correct |
1 ms |
332 KB |
Output is correct |
12 |
Correct |
1 ms |
332 KB |
Output is correct |
13 |
Correct |
1 ms |
204 KB |
Output is correct |
14 |
Correct |
1 ms |
204 KB |
Output is correct |
15 |
Correct |
1 ms |
332 KB |
Output is correct |
16 |
Correct |
1 ms |
204 KB |
Output is correct |
17 |
Correct |
1 ms |
204 KB |
Output is correct |
18 |
Correct |
1 ms |
204 KB |
Output is correct |
19 |
Correct |
1 ms |
204 KB |
Output is correct |
20 |
Correct |
1 ms |
204 KB |
Output is correct |
21 |
Correct |
1 ms |
332 KB |
Output is correct |
22 |
Correct |
1 ms |
204 KB |
Output is correct |
23 |
Correct |
1 ms |
332 KB |
Output is correct |
24 |
Correct |
1 ms |
332 KB |
Output is correct |
25 |
Correct |
1 ms |
332 KB |
Output is correct |
26 |
Correct |
1 ms |
332 KB |
Output is correct |
27 |
Correct |
3 ms |
844 KB |
Output is correct |
28 |
Correct |
2 ms |
844 KB |
Output is correct |
29 |
Correct |
2 ms |
844 KB |
Output is correct |
30 |
Correct |
2 ms |
588 KB |
Output is correct |
31 |
Correct |
2 ms |
460 KB |
Output is correct |
32 |
Correct |
1 ms |
332 KB |
Output is correct |
33 |
Correct |
3 ms |
460 KB |
Output is correct |
34 |
Correct |
2 ms |
716 KB |
Output is correct |
35 |
Correct |
1 ms |
460 KB |
Output is correct |
36 |
Correct |
2 ms |
716 KB |
Output is correct |
37 |
Correct |
2 ms |
716 KB |
Output is correct |
38 |
Correct |
2 ms |
844 KB |
Output is correct |
39 |
Correct |
3 ms |
844 KB |
Output is correct |
40 |
Correct |
2 ms |
588 KB |
Output is correct |
41 |
Correct |
4 ms |
716 KB |
Output is correct |
42 |
Correct |
548 ms |
53836 KB |
Output is correct |
43 |
Correct |
756 ms |
91456 KB |
Output is correct |
44 |
Correct |
128 ms |
18000 KB |
Output is correct |
45 |
Correct |
674 ms |
89396 KB |
Output is correct |
46 |
Correct |
317 ms |
125500 KB |
Output is correct |
47 |
Correct |
1 ms |
204 KB |
Output is correct |
48 |
Correct |
1 ms |
204 KB |
Output is correct |
49 |
Correct |
1 ms |
204 KB |
Output is correct |
50 |
Correct |
334 ms |
100688 KB |
Output is correct |
51 |
Correct |
315 ms |
81724 KB |
Output is correct |
52 |
Correct |
378 ms |
62172 KB |
Output is correct |
53 |
Correct |
398 ms |
62108 KB |
Output is correct |
54 |
Correct |
412 ms |
62140 KB |
Output is correct |
55 |
Correct |
559 ms |
54588 KB |
Output is correct |
56 |
Correct |
779 ms |
86868 KB |
Output is correct |
57 |
Correct |
716 ms |
94844 KB |
Output is correct |
58 |
Correct |
720 ms |
90692 KB |
Output is correct |
59 |
Correct |
1256 ms |
100072 KB |
Output is correct |
60 |
Correct |
548 ms |
72296 KB |
Output is correct |
61 |
Correct |
551 ms |
72312 KB |
Output is correct |
62 |
Correct |
585 ms |
59748 KB |
Output is correct |
63 |
Correct |
275 ms |
76136 KB |
Output is correct |
64 |
Correct |
6 ms |
2380 KB |
Output is correct |
65 |
Correct |
6 ms |
2380 KB |
Output is correct |
66 |
Correct |
621 ms |
59600 KB |
Output is correct |
67 |
Correct |
34 ms |
12856 KB |
Output is correct |
68 |
Correct |
57 ms |
21136 KB |
Output is correct |
69 |
Correct |
1310 ms |
97004 KB |
Output is correct |
70 |
Correct |
124 ms |
41908 KB |
Output is correct |
71 |
Correct |
362 ms |
125692 KB |
Output is correct |
72 |
Correct |
1394 ms |
100096 KB |
Output is correct |
73 |
Correct |
620 ms |
59796 KB |
Output is correct |