#include <bits/stdc++.h>
#include <cassert>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
typedef pair<int, int> pii;
#define MAX 301010
int N, M;
int cycle_chk[MAX];
int find_cycle(int v) {
if (cycle_chk[v] == v) return v;
else return cycle_chk[v] = find_cycle(cycle_chk[v]);
}
void merge_cycle(int u, int v) {
u = find_cycle(u);
v = find_cycle(v);
cycle_chk[u] = v;
}
int p[MAX];
int num[MAX];
set<int> keys[MAX];
queue<int> adj[MAX];
set<pii> mp[MAX];
int nxt[MAX];
vector<int> subv[MAX];
#define exists(st, v) (st.find(v) != st.end())
int find(int v) {
if (p[v] == v) return v;
return p[v] = find(p[v]);
}
queue<pii> lst;
int mn;
vector<int> mlist;
int mcnt[MAX]; //max move cnt
int merge_two(int u, int v) {
u = find(u);
v = find(v);
if (u == v) return u;
if (mcnt[u] >= mcnt[v]) swap(u, v);
mcnt[v] = max(mcnt[v], mcnt[u] + 1);
p[u] = v;
if (subv[u].size() > subv[v].size()) swap(subv[u], subv[v]);
for (auto x : subv[u]) subv[v].push_back(x);
num[v] += num[u];
for (auto x : keys[u]) {
keys[v].insert(x);
while (1) {
auto it = mp[v].lower_bound(pii(x, -1));
if (it == mp[v].end() || it->first != x) break;
adj[v].emplace(it->second);
mp[v].erase(it);
}
}
for (auto& [k, nv] : mp[u]) {
if (exists(keys[v], k)) adj[v].push(nv);
else mp[v].insert(pii(k, nv));
}
while (adj[u].size()) adj[v].push(adj[u].front()), adj[u].pop();
return v;
}
void merge(int u, int v) {
u = find(u);
v = find(v);
if (u == v) return;
int loc = v;
int m = v;
vector<int> all;
while (find(loc) != find(u)) {
loc = find(nxt[loc]);
all.push_back(loc);
}
for (auto x : all) v = merge_two(v, x);
while (adj[v].size()) {
int t = adj[v].front();
if (find(t) != find(v)) {
nxt[v] = t;
if (find_cycle(t) == find_cycle(v)) lst.emplace(v, t);
else merge_cycle(t, v);
break;
}
else adj[v].pop();
}
if (adj[v].empty()) {
if (mn > num[v]) {
mlist = subv[v];
mn = num[v];
}
else if (mn == num[v]) mlist.insert(mlist.end(), subv[v].begin(), subv[v].end());
}
}
vector<int> radj[MAX];
std::vector<int> find_reachable(std::vector<int> R, std::vector<int> U, std::vector<int> V, std::vector<int> C) {
N = R.size();
M = U.size();
int i;
for (i = 0; i < N; i++) p[i] = i, num[i] = 1, cycle_chk[i] = i, keys[i].emplace(R[i]), subv[i].push_back(i);
mn = N;
for (i = 0; i < M; i++) radj[U[i]].push_back(i), radj[V[i]].push_back(i);
auto to = [&](int v, int e) {
return U[e] + V[e] - v;
};
for (i = 0; i < N; i++) {
for (auto e : radj[i]) {
if (C[e] == R[i]) adj[i].emplace(to(i, e));
else mp[i].emplace(C[e], to(i, e));
}
}
for (i = 0; i < N; i++) {
nxt[i] = -1;
if (adj[i].size()) nxt[i] = adj[i].front();
}
for (i = 0; i < N; i++) {
if (~nxt[i]) {
int t = nxt[i];
if (find_cycle(t) == find_cycle(i)) lst.emplace(i, t);
else merge_cycle(i, t);
}
else {
mn = 1;
mlist.push_back(i);
}
}
int iters = 0;
while (lst.size()) {
int u, v;
tie(u, v) = lst.front();
lst.pop();
merge(u, v);
}
vector<int> ansv(N);
for (auto p : mlist) ansv[p] = 1;
return ansv;
}
Compilation message
keys.cpp: In function 'void merge(int, int)':
keys.cpp:79:6: warning: unused variable 'm' [-Wunused-variable]
79 | int m = v;
| ^
keys.cpp: In function 'std::vector<int> find_reachable(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
keys.cpp:138:6: warning: unused variable 'iters' [-Wunused-variable]
138 | int iters = 0;
| ^~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
135 ms |
245388 KB |
Output is correct |
2 |
Correct |
131 ms |
245356 KB |
Output is correct |
3 |
Correct |
138 ms |
245272 KB |
Output is correct |
4 |
Correct |
131 ms |
245272 KB |
Output is correct |
5 |
Correct |
131 ms |
245316 KB |
Output is correct |
6 |
Correct |
133 ms |
245328 KB |
Output is correct |
7 |
Correct |
131 ms |
245312 KB |
Output is correct |
8 |
Correct |
133 ms |
245272 KB |
Output is correct |
9 |
Correct |
132 ms |
245336 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
135 ms |
245388 KB |
Output is correct |
2 |
Correct |
131 ms |
245356 KB |
Output is correct |
3 |
Correct |
138 ms |
245272 KB |
Output is correct |
4 |
Correct |
131 ms |
245272 KB |
Output is correct |
5 |
Correct |
131 ms |
245316 KB |
Output is correct |
6 |
Correct |
133 ms |
245328 KB |
Output is correct |
7 |
Correct |
131 ms |
245312 KB |
Output is correct |
8 |
Correct |
133 ms |
245272 KB |
Output is correct |
9 |
Correct |
132 ms |
245336 KB |
Output is correct |
10 |
Correct |
143 ms |
245468 KB |
Output is correct |
11 |
Correct |
132 ms |
245408 KB |
Output is correct |
12 |
Correct |
132 ms |
245312 KB |
Output is correct |
13 |
Correct |
135 ms |
245324 KB |
Output is correct |
14 |
Correct |
133 ms |
245360 KB |
Output is correct |
15 |
Correct |
132 ms |
245348 KB |
Output is correct |
16 |
Correct |
134 ms |
245272 KB |
Output is correct |
17 |
Correct |
134 ms |
245336 KB |
Output is correct |
18 |
Correct |
132 ms |
245284 KB |
Output is correct |
19 |
Correct |
133 ms |
245276 KB |
Output is correct |
20 |
Correct |
131 ms |
245324 KB |
Output is correct |
21 |
Correct |
137 ms |
245280 KB |
Output is correct |
22 |
Correct |
133 ms |
245384 KB |
Output is correct |
23 |
Correct |
129 ms |
245332 KB |
Output is correct |
24 |
Correct |
133 ms |
245416 KB |
Output is correct |
25 |
Correct |
134 ms |
245324 KB |
Output is correct |
26 |
Correct |
136 ms |
245332 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
135 ms |
245388 KB |
Output is correct |
2 |
Correct |
131 ms |
245356 KB |
Output is correct |
3 |
Correct |
138 ms |
245272 KB |
Output is correct |
4 |
Correct |
131 ms |
245272 KB |
Output is correct |
5 |
Correct |
131 ms |
245316 KB |
Output is correct |
6 |
Correct |
133 ms |
245328 KB |
Output is correct |
7 |
Correct |
131 ms |
245312 KB |
Output is correct |
8 |
Correct |
133 ms |
245272 KB |
Output is correct |
9 |
Correct |
132 ms |
245336 KB |
Output is correct |
10 |
Correct |
143 ms |
245468 KB |
Output is correct |
11 |
Correct |
132 ms |
245408 KB |
Output is correct |
12 |
Correct |
132 ms |
245312 KB |
Output is correct |
13 |
Correct |
135 ms |
245324 KB |
Output is correct |
14 |
Correct |
133 ms |
245360 KB |
Output is correct |
15 |
Correct |
132 ms |
245348 KB |
Output is correct |
16 |
Correct |
134 ms |
245272 KB |
Output is correct |
17 |
Correct |
134 ms |
245336 KB |
Output is correct |
18 |
Correct |
132 ms |
245284 KB |
Output is correct |
19 |
Correct |
133 ms |
245276 KB |
Output is correct |
20 |
Correct |
131 ms |
245324 KB |
Output is correct |
21 |
Correct |
137 ms |
245280 KB |
Output is correct |
22 |
Correct |
133 ms |
245384 KB |
Output is correct |
23 |
Correct |
129 ms |
245332 KB |
Output is correct |
24 |
Correct |
133 ms |
245416 KB |
Output is correct |
25 |
Correct |
134 ms |
245324 KB |
Output is correct |
26 |
Correct |
136 ms |
245332 KB |
Output is correct |
27 |
Correct |
149 ms |
245712 KB |
Output is correct |
28 |
Correct |
134 ms |
245748 KB |
Output is correct |
29 |
Correct |
138 ms |
245828 KB |
Output is correct |
30 |
Correct |
140 ms |
245580 KB |
Output is correct |
31 |
Correct |
136 ms |
245484 KB |
Output is correct |
32 |
Correct |
135 ms |
245456 KB |
Output is correct |
33 |
Correct |
132 ms |
245580 KB |
Output is correct |
34 |
Correct |
135 ms |
245580 KB |
Output is correct |
35 |
Correct |
138 ms |
245572 KB |
Output is correct |
36 |
Correct |
135 ms |
245740 KB |
Output is correct |
37 |
Correct |
136 ms |
245868 KB |
Output is correct |
38 |
Correct |
143 ms |
245660 KB |
Output is correct |
39 |
Correct |
134 ms |
245896 KB |
Output is correct |
40 |
Correct |
133 ms |
245592 KB |
Output is correct |
41 |
Correct |
200 ms |
245796 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
135 ms |
245388 KB |
Output is correct |
2 |
Correct |
131 ms |
245356 KB |
Output is correct |
3 |
Correct |
138 ms |
245272 KB |
Output is correct |
4 |
Correct |
131 ms |
245272 KB |
Output is correct |
5 |
Correct |
131 ms |
245316 KB |
Output is correct |
6 |
Correct |
133 ms |
245328 KB |
Output is correct |
7 |
Correct |
131 ms |
245312 KB |
Output is correct |
8 |
Correct |
133 ms |
245272 KB |
Output is correct |
9 |
Correct |
132 ms |
245336 KB |
Output is correct |
10 |
Correct |
464 ms |
299936 KB |
Output is correct |
11 |
Correct |
695 ms |
318776 KB |
Output is correct |
12 |
Correct |
198 ms |
258588 KB |
Output is correct |
13 |
Correct |
531 ms |
308832 KB |
Output is correct |
14 |
Correct |
373 ms |
297792 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
135 ms |
245388 KB |
Output is correct |
2 |
Correct |
131 ms |
245356 KB |
Output is correct |
3 |
Correct |
138 ms |
245272 KB |
Output is correct |
4 |
Correct |
131 ms |
245272 KB |
Output is correct |
5 |
Correct |
131 ms |
245316 KB |
Output is correct |
6 |
Correct |
133 ms |
245328 KB |
Output is correct |
7 |
Correct |
131 ms |
245312 KB |
Output is correct |
8 |
Correct |
133 ms |
245272 KB |
Output is correct |
9 |
Correct |
132 ms |
245336 KB |
Output is correct |
10 |
Correct |
143 ms |
245468 KB |
Output is correct |
11 |
Correct |
132 ms |
245408 KB |
Output is correct |
12 |
Correct |
132 ms |
245312 KB |
Output is correct |
13 |
Correct |
135 ms |
245324 KB |
Output is correct |
14 |
Correct |
133 ms |
245360 KB |
Output is correct |
15 |
Correct |
132 ms |
245348 KB |
Output is correct |
16 |
Correct |
134 ms |
245272 KB |
Output is correct |
17 |
Correct |
134 ms |
245336 KB |
Output is correct |
18 |
Correct |
132 ms |
245284 KB |
Output is correct |
19 |
Correct |
133 ms |
245276 KB |
Output is correct |
20 |
Correct |
131 ms |
245324 KB |
Output is correct |
21 |
Correct |
137 ms |
245280 KB |
Output is correct |
22 |
Correct |
133 ms |
245384 KB |
Output is correct |
23 |
Correct |
129 ms |
245332 KB |
Output is correct |
24 |
Correct |
133 ms |
245416 KB |
Output is correct |
25 |
Correct |
134 ms |
245324 KB |
Output is correct |
26 |
Correct |
136 ms |
245332 KB |
Output is correct |
27 |
Correct |
149 ms |
245712 KB |
Output is correct |
28 |
Correct |
134 ms |
245748 KB |
Output is correct |
29 |
Correct |
138 ms |
245828 KB |
Output is correct |
30 |
Correct |
140 ms |
245580 KB |
Output is correct |
31 |
Correct |
136 ms |
245484 KB |
Output is correct |
32 |
Correct |
135 ms |
245456 KB |
Output is correct |
33 |
Correct |
132 ms |
245580 KB |
Output is correct |
34 |
Correct |
135 ms |
245580 KB |
Output is correct |
35 |
Correct |
138 ms |
245572 KB |
Output is correct |
36 |
Correct |
135 ms |
245740 KB |
Output is correct |
37 |
Correct |
136 ms |
245868 KB |
Output is correct |
38 |
Correct |
143 ms |
245660 KB |
Output is correct |
39 |
Correct |
134 ms |
245896 KB |
Output is correct |
40 |
Correct |
133 ms |
245592 KB |
Output is correct |
41 |
Correct |
200 ms |
245796 KB |
Output is correct |
42 |
Correct |
464 ms |
299936 KB |
Output is correct |
43 |
Correct |
695 ms |
318776 KB |
Output is correct |
44 |
Correct |
198 ms |
258588 KB |
Output is correct |
45 |
Correct |
531 ms |
308832 KB |
Output is correct |
46 |
Correct |
373 ms |
297792 KB |
Output is correct |
47 |
Correct |
136 ms |
245460 KB |
Output is correct |
48 |
Correct |
152 ms |
245344 KB |
Output is correct |
49 |
Correct |
133 ms |
245288 KB |
Output is correct |
50 |
Correct |
365 ms |
297132 KB |
Output is correct |
51 |
Correct |
364 ms |
298436 KB |
Output is correct |
52 |
Correct |
344 ms |
297160 KB |
Output is correct |
53 |
Correct |
331 ms |
297092 KB |
Output is correct |
54 |
Correct |
335 ms |
297240 KB |
Output is correct |
55 |
Correct |
524 ms |
306812 KB |
Output is correct |
56 |
Correct |
424 ms |
318240 KB |
Output is correct |
57 |
Correct |
404 ms |
319804 KB |
Output is correct |
58 |
Correct |
488 ms |
316604 KB |
Output is correct |
59 |
Correct |
831 ms |
322744 KB |
Output is correct |
60 |
Correct |
797 ms |
323604 KB |
Output is correct |
61 |
Correct |
856 ms |
323904 KB |
Output is correct |
62 |
Correct |
951 ms |
386572 KB |
Output is correct |
63 |
Correct |
402 ms |
311536 KB |
Output is correct |
64 |
Correct |
136 ms |
246348 KB |
Output is correct |
65 |
Correct |
136 ms |
246292 KB |
Output is correct |
66 |
Correct |
892 ms |
386584 KB |
Output is correct |
67 |
Correct |
157 ms |
251420 KB |
Output is correct |
68 |
Correct |
172 ms |
255408 KB |
Output is correct |
69 |
Correct |
855 ms |
338512 KB |
Output is correct |
70 |
Correct |
221 ms |
265328 KB |
Output is correct |
71 |
Correct |
424 ms |
304516 KB |
Output is correct |
72 |
Correct |
839 ms |
322700 KB |
Output is correct |
73 |
Correct |
892 ms |
386748 KB |
Output is correct |