/******************************
Author: jhnah917(Justice_Hui)
g++ -std=c++17 -DLOCAL
******************************/
#ifndef LOCAL
#include "split.h"
#endif
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
#define IDX(v, x) (lower_bound(all(v), x) - v.begin())
using namespace std;
using uint = unsigned;
using ll = long long;
using ull = unsigned long long;
using PII = pair<int, int>;
constexpr int SZ = 101010;
template<size_t _Sz> struct UnionFind {
int P[_Sz], W[_Sz];
UnionFind(){ clear(); }
void clear(){ iota(P, P+_Sz, 0); fill(W, W+_Sz, 1); }
int find(int v){ return v == P[v] ? v : P[v] = find(P[v]); }
bool merge(int u, int v){
u = find(u); v = find(v);
if(u == v) return false;
P[u] = v; W[v] += W[u];
return true;
}
};
int N, M, A, B, C, S[SZ], chk[SZ];
PII ORD[3];
vector<int> G[SZ], Tree[SZ], Comp[SZ];
UnionFind<SZ> UF;
int get_sz(int v, int b=-1){
S[v] = 1;
for(auto i : Tree[v]) if(i != b) S[v] += get_sz(i, v);
return S[v];
}
int get_cent(int v, int tot, int b=-1){
for(auto i : Tree[v]) if(i != b && S[i]*2 > tot) return get_cent(i, tot, v);
return v;
}
vector<int> dfs_subtree(int v, int b){
vector<int> ret;
function<void(int,int)> go = [&go,&ret](int v, int b){
ret.push_back(v);
for(auto i : Tree[v]) if(i != b) go(i, v);
};
go(v, b);
return move(ret);
}
void dfs_merge(int v, int b){
for(auto i : Tree[v]) if(i != b) UF.merge(v, i), dfs_merge(i, v);
}
vector<int> dfs_comp(int v){
vector<int> ret;
function<void(int)> go = [&go,&ret](int v){
chk[v] = 1; ret.push_back(v);
for(auto i : Comp[v]) if(!chk[i]) go(i);
};
go(v);
return move(ret);
}
int use[SZ];
vector<int> dfs_graph(int v){
vector<int> ret;
function<void(int)> go = [&ret,&go](int v){
chk[v] = 1; ret.push_back(v);
for(auto i : G[v]) if(!chk[i] && use[v] == use[i]) go(i);
};
go(v);
return move(ret);
}
vector<int> get_answer(const vector<int> &V){
vector<int> res(N, ORD[2].y);
memset(use, 0, sizeof use);
memset(chk, 0, sizeof chk);
for(auto i : V) use[i] = 1;
for(int i=0; i<N; i++){
if(chk[i]) continue;
auto dfn = dfs_graph(i);
dfn.resize(ORD[!use[i]].x);
for(auto j : dfn) res[j] = ORD[!use[i]].y;
}
return res;
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q){
N = n; M = p.size(); A = a; B = b; C = c;
ORD[0] = {A, 1}; ORD[1] = {B, 2}; ORD[2] = {C, 3};
sort(ORD, ORD+3);
UF.clear();
for(int i=0; i<M; i++){
int s = p[i], e = q[i];
if(UF.merge(s, e)) Tree[s].push_back(e), Tree[e].push_back(s);
G[s].push_back(e); G[e].push_back(s);
}
int cent = get_cent(0, get_sz(0));
for(auto i : Tree[cent]){
auto dfn = dfs_subtree(i, cent);
if(dfn.size() >= ORD[0].x) return get_answer(dfn);
}
UF.clear();
for(auto i : Tree[cent]) dfs_merge(i, cent);
for(int i=0; i<M; i++){
int s = UF.find(p[i]), e = UF.find(q[i]);
if(s == cent || e == cent || s == e) continue;
Comp[s].push_back(e); Comp[e].push_back(s);
}
memset(chk, 0, sizeof chk);
int pv = 0;
for(int i=0; i<N; i++){
if(i == cent || i != UF.find(i) || chk[i]) continue;
auto dfn = dfs_comp(i);
pv++;
int sum = 0;
for(auto j : dfn){
use[j] = pv;
if((sum += UF.W[j]) >= ORD[0].x) break;
}
if(sum < ORD[0].x) continue;
vector<int> res;
for(int j=0; j<N; j++) if(use[UF.find(j)] == pv) res.push_back(j);
return get_answer(res);
}
return vector<int>(N, 0);
}
#ifdef LOCAL
int main(){
int n, m, a, b, c;
assert(5 == scanf("%d%d%d%d%d", &n, &m, &a, &b, &c));
vector<int> p(m), q(m);
for(int i=0; i<m; i++) assert(2 == scanf("%d%d", &p[i], &q[i]));
vector<int> result = find_split(n, a, b, c, p, q);
for (int i=0; i<(int)result.size(); i++) printf("%s%d", ((i>0)?" ":""), result[i]);
printf("\n");
return 0;
}
#endif
Compilation message
split.cpp: In function 'std::vector<int> dfs_subtree(int, int)':
split.cpp:60:16: warning: moving a local object in a return statement prevents copy elision [-Wpessimizing-move]
60 | return move(ret);
| ~~~~^~~~~
split.cpp:60:16: note: remove 'std::move' call
split.cpp: In function 'std::vector<int> dfs_comp(int)':
split.cpp:74:16: warning: moving a local object in a return statement prevents copy elision [-Wpessimizing-move]
74 | return move(ret);
| ~~~~^~~~~
split.cpp:74:16: note: remove 'std::move' call
split.cpp: In function 'std::vector<int> dfs_graph(int)':
split.cpp:85:16: warning: moving a local object in a return statement prevents copy elision [-Wpessimizing-move]
85 | return move(ret);
| ~~~~^~~~~
split.cpp:85:16: note: remove 'std::move' call
split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:118:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
118 | if(dfn.size() >= ORD[0].x) return get_answer(dfn);
| ^
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
9068 KB |
ok, correct split |
2 |
Correct |
8 ms |
9216 KB |
ok, correct split |
3 |
Correct |
8 ms |
9068 KB |
ok, correct split |
4 |
Correct |
7 ms |
9068 KB |
ok, correct split |
5 |
Correct |
7 ms |
9068 KB |
ok, correct split |
6 |
Correct |
7 ms |
9068 KB |
ok, correct split |
7 |
Correct |
192 ms |
24228 KB |
ok, correct split |
8 |
Correct |
173 ms |
22500 KB |
ok, correct split |
9 |
Correct |
186 ms |
22176 KB |
ok, correct split |
10 |
Correct |
175 ms |
24228 KB |
ok, correct split |
11 |
Correct |
180 ms |
23332 KB |
ok, correct split |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
9068 KB |
ok, correct split |
2 |
Correct |
7 ms |
9068 KB |
ok, correct split |
3 |
Correct |
7 ms |
9068 KB |
ok, correct split |
4 |
Correct |
195 ms |
22248 KB |
ok, correct split |
5 |
Correct |
165 ms |
18516 KB |
ok, correct split |
6 |
Correct |
178 ms |
24228 KB |
ok, correct split |
7 |
Correct |
169 ms |
22308 KB |
ok, correct split |
8 |
Correct |
214 ms |
20584 KB |
ok, correct split |
9 |
Correct |
156 ms |
18280 KB |
ok, correct split |
10 |
Correct |
124 ms |
19164 KB |
ok, correct split |
11 |
Correct |
97 ms |
19164 KB |
ok, correct split |
12 |
Correct |
97 ms |
19164 KB |
ok, correct split |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
9068 KB |
ok, correct split |
2 |
Correct |
150 ms |
18580 KB |
ok, correct split |
3 |
Correct |
46 ms |
12916 KB |
ok, correct split |
4 |
Correct |
7 ms |
9068 KB |
ok, correct split |
5 |
Correct |
179 ms |
21028 KB |
ok, correct split |
6 |
Correct |
176 ms |
20900 KB |
ok, correct split |
7 |
Correct |
174 ms |
20944 KB |
ok, correct split |
8 |
Correct |
203 ms |
21324 KB |
ok, correct split |
9 |
Correct |
180 ms |
20812 KB |
ok, correct split |
10 |
Correct |
38 ms |
11756 KB |
ok, no valid answer |
11 |
Correct |
62 ms |
13292 KB |
ok, no valid answer |
12 |
Correct |
149 ms |
18280 KB |
ok, no valid answer |
13 |
Correct |
175 ms |
18028 KB |
ok, no valid answer |
14 |
Correct |
105 ms |
18524 KB |
ok, no valid answer |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
9068 KB |
ok, correct split |
2 |
Correct |
7 ms |
8684 KB |
ok, no valid answer |
3 |
Correct |
7 ms |
9068 KB |
ok, correct split |
4 |
Correct |
7 ms |
9068 KB |
ok, correct split |
5 |
Correct |
7 ms |
9216 KB |
ok, correct split |
6 |
Correct |
7 ms |
9068 KB |
ok, correct split |
7 |
Correct |
7 ms |
9068 KB |
ok, correct split |
8 |
Correct |
7 ms |
9068 KB |
ok, correct split |
9 |
Correct |
12 ms |
9324 KB |
ok, correct split |
10 |
Correct |
10 ms |
9324 KB |
ok, correct split |
11 |
Correct |
7 ms |
9068 KB |
ok, correct split |
12 |
Correct |
10 ms |
9324 KB |
ok, correct split |
13 |
Correct |
7 ms |
9068 KB |
ok, correct split |
14 |
Correct |
7 ms |
9068 KB |
ok, correct split |
15 |
Correct |
7 ms |
9068 KB |
ok, correct split |
16 |
Correct |
7 ms |
9068 KB |
ok, correct split |
17 |
Correct |
7 ms |
9068 KB |
ok, correct split |
18 |
Correct |
7 ms |
9068 KB |
ok, correct split |
19 |
Correct |
9 ms |
9068 KB |
ok, correct split |
20 |
Correct |
8 ms |
9068 KB |
ok, correct split |
21 |
Correct |
10 ms |
9324 KB |
ok, correct split |
22 |
Correct |
9 ms |
9324 KB |
ok, correct split |
23 |
Correct |
12 ms |
9324 KB |
ok, correct split |
24 |
Correct |
10 ms |
9324 KB |
ok, correct split |
25 |
Correct |
9 ms |
9324 KB |
ok, correct split |
26 |
Correct |
9 ms |
9324 KB |
ok, correct split |
27 |
Correct |
9 ms |
9324 KB |
ok, correct split |
28 |
Correct |
9 ms |
9324 KB |
ok, correct split |
29 |
Correct |
7 ms |
9068 KB |
ok, correct split |
30 |
Correct |
10 ms |
9324 KB |
ok, correct split |
31 |
Correct |
8 ms |
9068 KB |
ok, correct split |
32 |
Correct |
7 ms |
9068 KB |
ok, correct split |
33 |
Correct |
9 ms |
9068 KB |
ok, correct split |
34 |
Correct |
9 ms |
9324 KB |
ok, correct split |
35 |
Correct |
10 ms |
9324 KB |
ok, correct split |
36 |
Correct |
9 ms |
9196 KB |
ok, correct split |
37 |
Correct |
10 ms |
9324 KB |
ok, correct split |
38 |
Correct |
13 ms |
9324 KB |
ok, correct split |
39 |
Correct |
10 ms |
9324 KB |
ok, correct split |
40 |
Correct |
10 ms |
9324 KB |
ok, correct split |
41 |
Correct |
9 ms |
9196 KB |
ok, correct split |
42 |
Correct |
9 ms |
9196 KB |
ok, correct split |
43 |
Correct |
9 ms |
9324 KB |
ok, correct split |
44 |
Correct |
9 ms |
9324 KB |
ok, correct split |
45 |
Correct |
9 ms |
9324 KB |
ok, correct split |
46 |
Correct |
9 ms |
9344 KB |
ok, correct split |
47 |
Correct |
9 ms |
8940 KB |
ok, no valid answer |
48 |
Correct |
9 ms |
9324 KB |
ok, correct split |
49 |
Correct |
10 ms |
9324 KB |
ok, correct split |
50 |
Correct |
7 ms |
8684 KB |
ok, no valid answer |
51 |
Correct |
7 ms |
8684 KB |
ok, no valid answer |
52 |
Correct |
9 ms |
8812 KB |
ok, no valid answer |
53 |
Correct |
10 ms |
8940 KB |
ok, no valid answer |
54 |
Correct |
9 ms |
8812 KB |
ok, no valid answer |
55 |
Correct |
9 ms |
8940 KB |
ok, no valid answer |
56 |
Correct |
10 ms |
8940 KB |
ok, no valid answer |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
9068 KB |
ok, correct split |
2 |
Correct |
8 ms |
9216 KB |
ok, correct split |
3 |
Correct |
8 ms |
9068 KB |
ok, correct split |
4 |
Correct |
7 ms |
9068 KB |
ok, correct split |
5 |
Correct |
7 ms |
9068 KB |
ok, correct split |
6 |
Correct |
7 ms |
9068 KB |
ok, correct split |
7 |
Correct |
192 ms |
24228 KB |
ok, correct split |
8 |
Correct |
173 ms |
22500 KB |
ok, correct split |
9 |
Correct |
186 ms |
22176 KB |
ok, correct split |
10 |
Correct |
175 ms |
24228 KB |
ok, correct split |
11 |
Correct |
180 ms |
23332 KB |
ok, correct split |
12 |
Correct |
7 ms |
9068 KB |
ok, correct split |
13 |
Correct |
7 ms |
9068 KB |
ok, correct split |
14 |
Correct |
7 ms |
9068 KB |
ok, correct split |
15 |
Correct |
195 ms |
22248 KB |
ok, correct split |
16 |
Correct |
165 ms |
18516 KB |
ok, correct split |
17 |
Correct |
178 ms |
24228 KB |
ok, correct split |
18 |
Correct |
169 ms |
22308 KB |
ok, correct split |
19 |
Correct |
214 ms |
20584 KB |
ok, correct split |
20 |
Correct |
156 ms |
18280 KB |
ok, correct split |
21 |
Correct |
124 ms |
19164 KB |
ok, correct split |
22 |
Correct |
97 ms |
19164 KB |
ok, correct split |
23 |
Correct |
97 ms |
19164 KB |
ok, correct split |
24 |
Correct |
7 ms |
9068 KB |
ok, correct split |
25 |
Correct |
150 ms |
18580 KB |
ok, correct split |
26 |
Correct |
46 ms |
12916 KB |
ok, correct split |
27 |
Correct |
7 ms |
9068 KB |
ok, correct split |
28 |
Correct |
179 ms |
21028 KB |
ok, correct split |
29 |
Correct |
176 ms |
20900 KB |
ok, correct split |
30 |
Correct |
174 ms |
20944 KB |
ok, correct split |
31 |
Correct |
203 ms |
21324 KB |
ok, correct split |
32 |
Correct |
180 ms |
20812 KB |
ok, correct split |
33 |
Correct |
38 ms |
11756 KB |
ok, no valid answer |
34 |
Correct |
62 ms |
13292 KB |
ok, no valid answer |
35 |
Correct |
149 ms |
18280 KB |
ok, no valid answer |
36 |
Correct |
175 ms |
18028 KB |
ok, no valid answer |
37 |
Correct |
105 ms |
18524 KB |
ok, no valid answer |
38 |
Correct |
7 ms |
9068 KB |
ok, correct split |
39 |
Correct |
7 ms |
8684 KB |
ok, no valid answer |
40 |
Correct |
7 ms |
9068 KB |
ok, correct split |
41 |
Correct |
7 ms |
9068 KB |
ok, correct split |
42 |
Correct |
7 ms |
9216 KB |
ok, correct split |
43 |
Correct |
7 ms |
9068 KB |
ok, correct split |
44 |
Correct |
7 ms |
9068 KB |
ok, correct split |
45 |
Correct |
7 ms |
9068 KB |
ok, correct split |
46 |
Correct |
12 ms |
9324 KB |
ok, correct split |
47 |
Correct |
10 ms |
9324 KB |
ok, correct split |
48 |
Correct |
7 ms |
9068 KB |
ok, correct split |
49 |
Correct |
10 ms |
9324 KB |
ok, correct split |
50 |
Correct |
7 ms |
9068 KB |
ok, correct split |
51 |
Correct |
7 ms |
9068 KB |
ok, correct split |
52 |
Correct |
7 ms |
9068 KB |
ok, correct split |
53 |
Correct |
7 ms |
9068 KB |
ok, correct split |
54 |
Correct |
7 ms |
9068 KB |
ok, correct split |
55 |
Correct |
7 ms |
9068 KB |
ok, correct split |
56 |
Correct |
9 ms |
9068 KB |
ok, correct split |
57 |
Correct |
8 ms |
9068 KB |
ok, correct split |
58 |
Correct |
10 ms |
9324 KB |
ok, correct split |
59 |
Correct |
9 ms |
9324 KB |
ok, correct split |
60 |
Correct |
12 ms |
9324 KB |
ok, correct split |
61 |
Correct |
10 ms |
9324 KB |
ok, correct split |
62 |
Correct |
9 ms |
9324 KB |
ok, correct split |
63 |
Correct |
9 ms |
9324 KB |
ok, correct split |
64 |
Correct |
9 ms |
9324 KB |
ok, correct split |
65 |
Correct |
9 ms |
9324 KB |
ok, correct split |
66 |
Correct |
7 ms |
9068 KB |
ok, correct split |
67 |
Correct |
10 ms |
9324 KB |
ok, correct split |
68 |
Correct |
8 ms |
9068 KB |
ok, correct split |
69 |
Correct |
7 ms |
9068 KB |
ok, correct split |
70 |
Correct |
9 ms |
9068 KB |
ok, correct split |
71 |
Correct |
9 ms |
9324 KB |
ok, correct split |
72 |
Correct |
10 ms |
9324 KB |
ok, correct split |
73 |
Correct |
9 ms |
9196 KB |
ok, correct split |
74 |
Correct |
10 ms |
9324 KB |
ok, correct split |
75 |
Correct |
13 ms |
9324 KB |
ok, correct split |
76 |
Correct |
10 ms |
9324 KB |
ok, correct split |
77 |
Correct |
10 ms |
9324 KB |
ok, correct split |
78 |
Correct |
9 ms |
9196 KB |
ok, correct split |
79 |
Correct |
9 ms |
9196 KB |
ok, correct split |
80 |
Correct |
9 ms |
9324 KB |
ok, correct split |
81 |
Correct |
9 ms |
9324 KB |
ok, correct split |
82 |
Correct |
9 ms |
9324 KB |
ok, correct split |
83 |
Correct |
9 ms |
9344 KB |
ok, correct split |
84 |
Correct |
9 ms |
8940 KB |
ok, no valid answer |
85 |
Correct |
9 ms |
9324 KB |
ok, correct split |
86 |
Correct |
10 ms |
9324 KB |
ok, correct split |
87 |
Correct |
7 ms |
8684 KB |
ok, no valid answer |
88 |
Correct |
7 ms |
8684 KB |
ok, no valid answer |
89 |
Correct |
9 ms |
8812 KB |
ok, no valid answer |
90 |
Correct |
10 ms |
8940 KB |
ok, no valid answer |
91 |
Correct |
9 ms |
8812 KB |
ok, no valid answer |
92 |
Correct |
9 ms |
8940 KB |
ok, no valid answer |
93 |
Correct |
10 ms |
8940 KB |
ok, no valid answer |
94 |
Correct |
179 ms |
19496 KB |
ok, correct split |
95 |
Correct |
243 ms |
23400 KB |
ok, correct split |
96 |
Correct |
246 ms |
22280 KB |
ok, correct split |
97 |
Correct |
48 ms |
12908 KB |
ok, correct split |
98 |
Correct |
50 ms |
13036 KB |
ok, correct split |
99 |
Correct |
67 ms |
14700 KB |
ok, correct split |
100 |
Correct |
217 ms |
21096 KB |
ok, correct split |
101 |
Correct |
217 ms |
20244 KB |
ok, correct split |
102 |
Correct |
205 ms |
21604 KB |
ok, correct split |
103 |
Correct |
208 ms |
21216 KB |
ok, correct split |
104 |
Correct |
159 ms |
21464 KB |
ok, correct split |
105 |
Correct |
85 ms |
14836 KB |
ok, correct split |
106 |
Correct |
163 ms |
21084 KB |
ok, correct split |
107 |
Correct |
146 ms |
18488 KB |
ok, correct split |
108 |
Correct |
156 ms |
18608 KB |
ok, correct split |
109 |
Correct |
228 ms |
20640 KB |
ok, correct split |
110 |
Correct |
270 ms |
22368 KB |
ok, correct split |
111 |
Correct |
247 ms |
22368 KB |
ok, correct split |
112 |
Correct |
251 ms |
22844 KB |
ok, correct split |
113 |
Correct |
244 ms |
22880 KB |
ok, correct split |
114 |
Correct |
23 ms |
10476 KB |
ok, correct split |
115 |
Correct |
22 ms |
10476 KB |
ok, correct split |
116 |
Correct |
215 ms |
20576 KB |
ok, correct split |
117 |
Correct |
213 ms |
20536 KB |
ok, correct split |
118 |
Correct |
164 ms |
18332 KB |
ok, correct split |
119 |
Correct |
211 ms |
18408 KB |
ok, correct split |
120 |
Correct |
219 ms |
22192 KB |
ok, correct split |
121 |
Correct |
152 ms |
17772 KB |
ok, no valid answer |
122 |
Correct |
145 ms |
18092 KB |
ok, no valid answer |
123 |
Correct |
226 ms |
19968 KB |
ok, no valid answer |
124 |
Correct |
242 ms |
20204 KB |
ok, no valid answer |
125 |
Correct |
145 ms |
19420 KB |
ok, no valid answer |
126 |
Correct |
90 ms |
17628 KB |
ok, no valid answer |
127 |
Correct |
172 ms |
20060 KB |
ok, no valid answer |