#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
void debug_out(){cerr << endl;}
template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T){
cerr << H << ' ';
debug_out(T...);
}
#define debug(...) cerr << "(" << #__VA_ARGS__ << "): ", debug_out(__VA_ARGS__)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)
const int maxn = 3e5 + 10;
int n, m, r[maxn], comp[maxn], st[maxn];
vector<pii> g[maxn];
int ans = maxn;
vector<int> res, ver[maxn], rej[maxn];
bool vis[maxn], bad[maxn], mark[maxn], expand;
vector<int> going;
void merge(int u, int v){
bool flg = true;
if ((u = comp[u]) == (v = comp[v])) return;
// debug(u, v);
if (ver[u].size() < ver[v].size()){
swap(u, v);
flg = false;
}
for (auto x: ver[v]){
if (x == v) continue;
comp[x] = u;
ver[u].push_back(x);
}
if (flg) st[u] = st[v];
comp[v] = u;
ver[u].push_back(v);
// debug(u, st[u]);
}
void dfs(int v){
// debug("dfs", v);
going.push_back(v);
vis[v] = true;
mark[r[v]] = true;
while(!rej[r[v]].empty() && !expand){
int u = rej[r[v]].back();
rej[r[v]].pop_back();
if (bad[u]){
int x = comp[v];
for (auto y: ver[x]){
bad[y] = true;
}
expand = true;
return;
}
else if (comp[u] != comp[v]){
merge(v, u);
expand = true;
return;
}
else if (!vis[u]) dfs(u);
}
for (auto [u, w]: g[v]){
if (expand) return;
if (!mark[w]){
rej[w].push_back(u);
continue;
}
if (bad[u]){
int x = comp[v];
for (auto y: ver[x]){
bad[y] = true;
}
expand = true;
return;
}
else if (comp[u] != comp[v]){
merge(v, u);
expand = true;
return;
}
else if (!vis[u]) dfs(u);
}
}
vector<int> find_reachable(vector<int> R, vector<int> U, vector<int> V, vector<int> C) {
n = R.size();
m = C.size();
for (int i = 0; i < n; i++){
r[i] = R[i];
comp[i] = i;
st[i] = i;
ver[i].push_back(i);
}
for (int i = 0; i < m; i++){
g[U[i]].push_back({V[i], C[i]});
g[V[i]].push_back({U[i], C[i]});
}
int cnt = 1;
for (int iii = 0; iii < 20; iii++) {
// debug(cnt);
cnt++;
memset(vis, false, sizeof vis);
for (int i = 0; i < n; i++){
int v = st[comp[i]];
if (!vis[v] && !bad[v]){
expand = false;
// debug(v);
going.clear();
dfs(v);
// debug(expand);
if (!expand){
vector<int> tmp;
for (auto x: ver[comp[i]]){
bad[x] = true;
if (vis[x]) tmp.push_back(x);
vis[x] = true;
}
if (tmp.size() < ans){
ans = tmp.size();
res.clear();
}
if (tmp.size() == ans){
for (auto x: tmp) res.push_back(x);
}
}
else{
vis[st[comp[i]]] = true;
}
v = comp[v];
for (auto x: going){
mark[r[x]] = false;
for (auto [u, w]: g[x]){
rej[w].clear();
}
}
}
}
}
vector<int> answer(n, 0);
for (auto x: res) answer[x] = 1;
return answer;
}
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:130:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
130 | if (tmp.size() < ans){
| ~~~~~~~~~~~^~~~~
keys.cpp:134:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
134 | if (tmp.size() == ans){
| ~~~~~~~~~~~^~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
11 ms |
21716 KB |
Output is correct |
2 |
Correct |
11 ms |
21728 KB |
Output is correct |
3 |
Correct |
11 ms |
21664 KB |
Output is correct |
4 |
Correct |
11 ms |
21716 KB |
Output is correct |
5 |
Correct |
11 ms |
21640 KB |
Output is correct |
6 |
Correct |
11 ms |
21716 KB |
Output is correct |
7 |
Correct |
11 ms |
21716 KB |
Output is correct |
8 |
Correct |
11 ms |
21740 KB |
Output is correct |
9 |
Correct |
11 ms |
21716 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
11 ms |
21716 KB |
Output is correct |
2 |
Correct |
11 ms |
21728 KB |
Output is correct |
3 |
Correct |
11 ms |
21664 KB |
Output is correct |
4 |
Correct |
11 ms |
21716 KB |
Output is correct |
5 |
Correct |
11 ms |
21640 KB |
Output is correct |
6 |
Correct |
11 ms |
21716 KB |
Output is correct |
7 |
Correct |
11 ms |
21716 KB |
Output is correct |
8 |
Correct |
11 ms |
21740 KB |
Output is correct |
9 |
Correct |
11 ms |
21716 KB |
Output is correct |
10 |
Correct |
11 ms |
21716 KB |
Output is correct |
11 |
Correct |
10 ms |
21716 KB |
Output is correct |
12 |
Correct |
10 ms |
21716 KB |
Output is correct |
13 |
Correct |
10 ms |
21716 KB |
Output is correct |
14 |
Correct |
10 ms |
21692 KB |
Output is correct |
15 |
Correct |
10 ms |
21692 KB |
Output is correct |
16 |
Correct |
11 ms |
21716 KB |
Output is correct |
17 |
Correct |
10 ms |
21716 KB |
Output is correct |
18 |
Correct |
11 ms |
21772 KB |
Output is correct |
19 |
Correct |
10 ms |
21724 KB |
Output is correct |
20 |
Correct |
12 ms |
21716 KB |
Output is correct |
21 |
Correct |
11 ms |
21692 KB |
Output is correct |
22 |
Correct |
10 ms |
21680 KB |
Output is correct |
23 |
Correct |
11 ms |
21716 KB |
Output is correct |
24 |
Correct |
11 ms |
21716 KB |
Output is correct |
25 |
Correct |
11 ms |
21716 KB |
Output is correct |
26 |
Correct |
11 ms |
21716 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
11 ms |
21716 KB |
Output is correct |
2 |
Correct |
11 ms |
21728 KB |
Output is correct |
3 |
Correct |
11 ms |
21664 KB |
Output is correct |
4 |
Correct |
11 ms |
21716 KB |
Output is correct |
5 |
Correct |
11 ms |
21640 KB |
Output is correct |
6 |
Correct |
11 ms |
21716 KB |
Output is correct |
7 |
Correct |
11 ms |
21716 KB |
Output is correct |
8 |
Correct |
11 ms |
21740 KB |
Output is correct |
9 |
Correct |
11 ms |
21716 KB |
Output is correct |
10 |
Correct |
11 ms |
21716 KB |
Output is correct |
11 |
Correct |
10 ms |
21716 KB |
Output is correct |
12 |
Correct |
10 ms |
21716 KB |
Output is correct |
13 |
Correct |
10 ms |
21716 KB |
Output is correct |
14 |
Correct |
10 ms |
21692 KB |
Output is correct |
15 |
Correct |
10 ms |
21692 KB |
Output is correct |
16 |
Correct |
11 ms |
21716 KB |
Output is correct |
17 |
Correct |
10 ms |
21716 KB |
Output is correct |
18 |
Correct |
11 ms |
21772 KB |
Output is correct |
19 |
Correct |
10 ms |
21724 KB |
Output is correct |
20 |
Correct |
12 ms |
21716 KB |
Output is correct |
21 |
Correct |
11 ms |
21692 KB |
Output is correct |
22 |
Correct |
10 ms |
21680 KB |
Output is correct |
23 |
Correct |
11 ms |
21716 KB |
Output is correct |
24 |
Correct |
11 ms |
21716 KB |
Output is correct |
25 |
Correct |
11 ms |
21716 KB |
Output is correct |
26 |
Correct |
11 ms |
21716 KB |
Output is correct |
27 |
Correct |
11 ms |
22052 KB |
Output is correct |
28 |
Correct |
14 ms |
22040 KB |
Output is correct |
29 |
Correct |
12 ms |
22000 KB |
Output is correct |
30 |
Correct |
14 ms |
21884 KB |
Output is correct |
31 |
Correct |
11 ms |
21884 KB |
Output is correct |
32 |
Correct |
10 ms |
21716 KB |
Output is correct |
33 |
Correct |
13 ms |
21760 KB |
Output is correct |
34 |
Correct |
11 ms |
21976 KB |
Output is correct |
35 |
Correct |
11 ms |
21844 KB |
Output is correct |
36 |
Correct |
12 ms |
21972 KB |
Output is correct |
37 |
Correct |
12 ms |
22192 KB |
Output is correct |
38 |
Correct |
11 ms |
22016 KB |
Output is correct |
39 |
Correct |
12 ms |
22184 KB |
Output is correct |
40 |
Correct |
11 ms |
21844 KB |
Output is correct |
41 |
Correct |
12 ms |
21844 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
11 ms |
21716 KB |
Output is correct |
2 |
Correct |
11 ms |
21728 KB |
Output is correct |
3 |
Correct |
11 ms |
21664 KB |
Output is correct |
4 |
Correct |
11 ms |
21716 KB |
Output is correct |
5 |
Correct |
11 ms |
21640 KB |
Output is correct |
6 |
Correct |
11 ms |
21716 KB |
Output is correct |
7 |
Correct |
11 ms |
21716 KB |
Output is correct |
8 |
Correct |
11 ms |
21740 KB |
Output is correct |
9 |
Correct |
11 ms |
21716 KB |
Output is correct |
10 |
Correct |
184 ms |
53316 KB |
Output is correct |
11 |
Correct |
205 ms |
64824 KB |
Output is correct |
12 |
Correct |
45 ms |
29256 KB |
Output is correct |
13 |
Correct |
269 ms |
58832 KB |
Output is correct |
14 |
Correct |
172 ms |
102156 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
11 ms |
21716 KB |
Output is correct |
2 |
Correct |
11 ms |
21728 KB |
Output is correct |
3 |
Correct |
11 ms |
21664 KB |
Output is correct |
4 |
Correct |
11 ms |
21716 KB |
Output is correct |
5 |
Correct |
11 ms |
21640 KB |
Output is correct |
6 |
Correct |
11 ms |
21716 KB |
Output is correct |
7 |
Correct |
11 ms |
21716 KB |
Output is correct |
8 |
Correct |
11 ms |
21740 KB |
Output is correct |
9 |
Correct |
11 ms |
21716 KB |
Output is correct |
10 |
Correct |
11 ms |
21716 KB |
Output is correct |
11 |
Correct |
10 ms |
21716 KB |
Output is correct |
12 |
Correct |
10 ms |
21716 KB |
Output is correct |
13 |
Correct |
10 ms |
21716 KB |
Output is correct |
14 |
Correct |
10 ms |
21692 KB |
Output is correct |
15 |
Correct |
10 ms |
21692 KB |
Output is correct |
16 |
Correct |
11 ms |
21716 KB |
Output is correct |
17 |
Correct |
10 ms |
21716 KB |
Output is correct |
18 |
Correct |
11 ms |
21772 KB |
Output is correct |
19 |
Correct |
10 ms |
21724 KB |
Output is correct |
20 |
Correct |
12 ms |
21716 KB |
Output is correct |
21 |
Correct |
11 ms |
21692 KB |
Output is correct |
22 |
Correct |
10 ms |
21680 KB |
Output is correct |
23 |
Correct |
11 ms |
21716 KB |
Output is correct |
24 |
Correct |
11 ms |
21716 KB |
Output is correct |
25 |
Correct |
11 ms |
21716 KB |
Output is correct |
26 |
Correct |
11 ms |
21716 KB |
Output is correct |
27 |
Correct |
11 ms |
22052 KB |
Output is correct |
28 |
Correct |
14 ms |
22040 KB |
Output is correct |
29 |
Correct |
12 ms |
22000 KB |
Output is correct |
30 |
Correct |
14 ms |
21884 KB |
Output is correct |
31 |
Correct |
11 ms |
21884 KB |
Output is correct |
32 |
Correct |
10 ms |
21716 KB |
Output is correct |
33 |
Correct |
13 ms |
21760 KB |
Output is correct |
34 |
Correct |
11 ms |
21976 KB |
Output is correct |
35 |
Correct |
11 ms |
21844 KB |
Output is correct |
36 |
Correct |
12 ms |
21972 KB |
Output is correct |
37 |
Correct |
12 ms |
22192 KB |
Output is correct |
38 |
Correct |
11 ms |
22016 KB |
Output is correct |
39 |
Correct |
12 ms |
22184 KB |
Output is correct |
40 |
Correct |
11 ms |
21844 KB |
Output is correct |
41 |
Correct |
12 ms |
21844 KB |
Output is correct |
42 |
Correct |
184 ms |
53316 KB |
Output is correct |
43 |
Correct |
205 ms |
64824 KB |
Output is correct |
44 |
Correct |
45 ms |
29256 KB |
Output is correct |
45 |
Correct |
269 ms |
58832 KB |
Output is correct |
46 |
Correct |
172 ms |
102156 KB |
Output is correct |
47 |
Correct |
11 ms |
21760 KB |
Output is correct |
48 |
Correct |
11 ms |
21708 KB |
Output is correct |
49 |
Correct |
10 ms |
21692 KB |
Output is correct |
50 |
Correct |
150 ms |
82316 KB |
Output is correct |
51 |
Correct |
179 ms |
83836 KB |
Output is correct |
52 |
Correct |
198 ms |
56376 KB |
Output is correct |
53 |
Correct |
236 ms |
56312 KB |
Output is correct |
54 |
Correct |
212 ms |
56360 KB |
Output is correct |
55 |
Correct |
209 ms |
58916 KB |
Output is correct |
56 |
Correct |
348 ms |
71872 KB |
Output is correct |
57 |
Correct |
204 ms |
67588 KB |
Output is correct |
58 |
Correct |
238 ms |
75956 KB |
Output is correct |
59 |
Correct |
356 ms |
76468 KB |
Output is correct |
60 |
Correct |
336 ms |
89852 KB |
Output is correct |
61 |
Correct |
384 ms |
91132 KB |
Output is correct |
62 |
Correct |
549 ms |
73592 KB |
Output is correct |
63 |
Correct |
166 ms |
57200 KB |
Output is correct |
64 |
Correct |
14 ms |
23152 KB |
Output is correct |
65 |
Correct |
13 ms |
23256 KB |
Output is correct |
66 |
Correct |
470 ms |
67440 KB |
Output is correct |
67 |
Correct |
27 ms |
30364 KB |
Output is correct |
68 |
Correct |
38 ms |
36436 KB |
Output is correct |
69 |
Correct |
333 ms |
76540 KB |
Output is correct |
70 |
Correct |
65 ms |
50824 KB |
Output is correct |
71 |
Correct |
222 ms |
106980 KB |
Output is correct |
72 |
Correct |
363 ms |
76608 KB |
Output is correct |
73 |
Correct |
489 ms |
73424 KB |
Output is correct |