#include "split.h"
#include <bits/stdc++.h>
using namespace std;
const int SZ = 2e5 + 5;
vector <int> vg[SZ], va[SZ];
int n;
int d[SZ], Max[SZ];
bool viz[SZ];
void dfs(int nod){
viz[nod] = 1; d[nod] = 1;
for(auto it : vg[nod]){
if(viz[it]) continue ;
va[it].push_back(nod);
va[nod].push_back(it);
dfs(it);
d[nod] += d[it];
Max[nod] = max(Max[nod], d[it]);
}
}
int find_centroid(int nod){
viz[nod] = 1;
if(max(Max[nod], n - d[nod]) <= n / 2) return nod;
for(auto it : va[nod]){
if(viz[it]) continue ;
int x = find_centroid(it);
if(x) return x;
}
return 0;
}
vector <int> comp[SZ];
int id[SZ], RG[SZ];
inline int find(int x){
int R = x;
while(R != id[R]) R = id[R];
while(id[x] != R){
int aux = id[x];
id[x] = R;
x = aux;
}
return R;
}
inline void unite(int x, int y){
if(x == y) return ;
if(RG[x] >= RG[y]) id[y] = x, RG[x] += RG[y];
else id[x] = y, RG[y] += RG[x];
}
void make_comp(int nod, int NR){
comp[NR].push_back(nod);
viz[nod] = 1;
for(auto it : va[nod]){
if(viz[it]) continue ;
unite(find(it), find(nod));
make_comp(it, NR);
}
}
void merge_comp(int nod, int &am, int a){
if(am >= a) return ;
viz[nod] = 1;
for(auto it : vg[nod]){
if(viz[it]) continue ;
if(find(it) == find(nod)) merge_comp(it, am, a);
else{
unite(find(nod), find(it));
am = RG[find(nod)];
if(am >= a) return ;
merge_comp(it, am, a);
}
}
return ;
}
int cul[SZ];
int rem;
void paint_comp(int nod, int c){
if(rem == 0) return ;
viz[nod] = 1;
--rem;
cul[nod] = c;
for(auto it : vg[nod]){
if(viz[it] || cul[it] || find(it) != find(nod)) continue ;
if(rem) paint_comp(it, c);
}
}
vector<int> res;
vector<int> find_split(int N, int a, int b, int c, vector<int> p, vector<int> q) {
n = N;
res.resize(n);
int m = p.size();
for(int i = 0; i < m ; ++i){
vg[p[i] + 1].push_back(q[i] + 1);
vg[q[i] + 1].push_back(p[i] + 1);
}
int ca = 1, cb = 2, cc = 3;
if(a > b) swap(a, b), swap(ca, cb);
if(a > c) swap(a, c), swap(ca, cc);
if(b > c) swap(b, c), swap(cb, cc);
for(int i = 1; i <= n ; ++i) id[i] = i, RG[i] = 1;
dfs(1);
memset(viz, 0, sizeof(viz));
int nod = find_centroid(1);
memset(viz, 0, sizeof(viz));
int NR = 0;
viz[nod] = 1;
for(auto it : va[nod]){
make_comp(it, NR);
NR++;
}
bool found = false;
int wh = 0;
for(int i = 0; i < NR ; ++i){
if(comp[i].size() >= a){
found = true;
wh = comp[i][0];
break ;
}
}
//cerr << found << endl;
if(!found){
memset(viz, 0, sizeof(viz));
viz[nod] = 1;
for(int i = 0; i < NR ; ++i){
int x = RG[find(comp[i][0])];
merge_comp(comp[i][0], x, a);
if(x >= a){
wh = comp[i][0];
break ;
}
}
}
if(wh == 0) return res;
memset(viz, 0, sizeof(viz));
viz[nod] = 1;
rem = a;
paint_comp(wh, ca);
for(int i = 1; i <= n ; ++i) unite(find(i), find(nod));
memset(viz, 0, sizeof(viz));
rem = b;
paint_comp(nod, cb);
for(int i = 0; i < n ; ++i){
if(cul[i + 1] == 0) cul[i + 1] = cc;
res[i] = cul[i + 1];
}
return res;
}
Compilation message
split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:135:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(comp[i].size() >= a){
~~~~~~~~~~~~~~~^~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
14584 KB |
ok, correct split |
2 |
Correct |
15 ms |
14584 KB |
ok, correct split |
3 |
Correct |
14 ms |
14584 KB |
ok, correct split |
4 |
Correct |
15 ms |
14584 KB |
ok, correct split |
5 |
Correct |
15 ms |
14584 KB |
ok, correct split |
6 |
Correct |
15 ms |
14584 KB |
ok, correct split |
7 |
Correct |
196 ms |
31732 KB |
ok, correct split |
8 |
Correct |
190 ms |
29816 KB |
ok, correct split |
9 |
Correct |
180 ms |
29300 KB |
ok, correct split |
10 |
Correct |
161 ms |
31988 KB |
ok, correct split |
11 |
Correct |
172 ms |
32116 KB |
ok, correct split |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
14584 KB |
ok, correct split |
2 |
Correct |
16 ms |
14584 KB |
ok, correct split |
3 |
Correct |
14 ms |
14584 KB |
ok, correct split |
4 |
Correct |
200 ms |
29628 KB |
ok, correct split |
5 |
Correct |
150 ms |
26080 KB |
ok, correct split |
6 |
Correct |
171 ms |
31964 KB |
ok, correct split |
7 |
Correct |
206 ms |
29680 KB |
ok, correct split |
8 |
Correct |
233 ms |
27768 KB |
ok, correct split |
9 |
Correct |
181 ms |
25780 KB |
ok, correct split |
10 |
Correct |
113 ms |
28784 KB |
ok, correct split |
11 |
Correct |
125 ms |
28656 KB |
ok, correct split |
12 |
Correct |
106 ms |
28656 KB |
ok, correct split |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
14584 KB |
ok, correct split |
2 |
Correct |
142 ms |
25976 KB |
ok, correct split |
3 |
Correct |
57 ms |
19084 KB |
ok, correct split |
4 |
Correct |
16 ms |
14584 KB |
ok, correct split |
5 |
Correct |
203 ms |
27768 KB |
ok, correct split |
6 |
Correct |
171 ms |
27768 KB |
ok, correct split |
7 |
Correct |
200 ms |
27512 KB |
ok, correct split |
8 |
Correct |
184 ms |
28512 KB |
ok, correct split |
9 |
Correct |
189 ms |
27384 KB |
ok, correct split |
10 |
Correct |
49 ms |
18296 KB |
ok, no valid answer |
11 |
Correct |
69 ms |
20216 KB |
ok, no valid answer |
12 |
Correct |
127 ms |
27384 KB |
ok, no valid answer |
13 |
Correct |
166 ms |
25848 KB |
ok, no valid answer |
14 |
Correct |
115 ms |
28272 KB |
ok, no valid answer |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
14584 KB |
ok, correct split |
2 |
Correct |
14 ms |
14584 KB |
ok, no valid answer |
3 |
Correct |
15 ms |
14584 KB |
ok, correct split |
4 |
Correct |
18 ms |
14584 KB |
ok, correct split |
5 |
Correct |
16 ms |
14584 KB |
ok, correct split |
6 |
Correct |
16 ms |
14584 KB |
ok, correct split |
7 |
Correct |
14 ms |
14584 KB |
ok, correct split |
8 |
Correct |
16 ms |
14584 KB |
ok, correct split |
9 |
Correct |
18 ms |
14968 KB |
ok, correct split |
10 |
Correct |
17 ms |
15000 KB |
ok, correct split |
11 |
Correct |
17 ms |
14712 KB |
ok, correct split |
12 |
Correct |
19 ms |
14968 KB |
ok, correct split |
13 |
Correct |
15 ms |
14584 KB |
ok, correct split |
14 |
Correct |
15 ms |
14584 KB |
ok, correct split |
15 |
Correct |
15 ms |
14584 KB |
ok, correct split |
16 |
Correct |
15 ms |
14584 KB |
ok, correct split |
17 |
Correct |
14 ms |
14584 KB |
ok, correct split |
18 |
Correct |
15 ms |
14584 KB |
ok, correct split |
19 |
Correct |
15 ms |
14712 KB |
ok, correct split |
20 |
Correct |
17 ms |
14712 KB |
ok, correct split |
21 |
Correct |
19 ms |
15020 KB |
ok, correct split |
22 |
Correct |
18 ms |
15096 KB |
ok, correct split |
23 |
Correct |
16 ms |
14968 KB |
ok, correct split |
24 |
Correct |
17 ms |
14968 KB |
ok, correct split |
25 |
Correct |
18 ms |
14968 KB |
ok, correct split |
26 |
Correct |
17 ms |
14968 KB |
ok, correct split |
27 |
Correct |
17 ms |
15096 KB |
ok, correct split |
28 |
Correct |
18 ms |
15096 KB |
ok, correct split |
29 |
Correct |
15 ms |
14712 KB |
ok, correct split |
30 |
Correct |
17 ms |
15100 KB |
ok, correct split |
31 |
Correct |
16 ms |
14712 KB |
ok, correct split |
32 |
Correct |
15 ms |
14712 KB |
ok, correct split |
33 |
Correct |
15 ms |
14712 KB |
ok, correct split |
34 |
Correct |
17 ms |
14972 KB |
ok, correct split |
35 |
Correct |
18 ms |
14968 KB |
ok, correct split |
36 |
Correct |
17 ms |
14968 KB |
ok, correct split |
37 |
Correct |
19 ms |
15096 KB |
ok, correct split |
38 |
Correct |
18 ms |
14968 KB |
ok, correct split |
39 |
Correct |
18 ms |
15096 KB |
ok, correct split |
40 |
Correct |
17 ms |
14968 KB |
ok, correct split |
41 |
Correct |
17 ms |
14840 KB |
ok, correct split |
42 |
Correct |
16 ms |
14840 KB |
ok, correct split |
43 |
Correct |
18 ms |
14968 KB |
ok, correct split |
44 |
Correct |
19 ms |
15096 KB |
ok, correct split |
45 |
Correct |
19 ms |
14972 KB |
ok, correct split |
46 |
Correct |
17 ms |
14968 KB |
ok, correct split |
47 |
Correct |
17 ms |
14968 KB |
ok, no valid answer |
48 |
Correct |
17 ms |
14968 KB |
ok, correct split |
49 |
Correct |
20 ms |
14968 KB |
ok, correct split |
50 |
Correct |
15 ms |
14584 KB |
ok, no valid answer |
51 |
Correct |
15 ms |
14584 KB |
ok, no valid answer |
52 |
Correct |
16 ms |
14968 KB |
ok, no valid answer |
53 |
Correct |
18 ms |
14968 KB |
ok, no valid answer |
54 |
Correct |
17 ms |
14968 KB |
ok, no valid answer |
55 |
Correct |
18 ms |
14968 KB |
ok, no valid answer |
56 |
Correct |
20 ms |
14968 KB |
ok, no valid answer |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
14584 KB |
ok, correct split |
2 |
Correct |
15 ms |
14584 KB |
ok, correct split |
3 |
Correct |
14 ms |
14584 KB |
ok, correct split |
4 |
Correct |
15 ms |
14584 KB |
ok, correct split |
5 |
Correct |
15 ms |
14584 KB |
ok, correct split |
6 |
Correct |
15 ms |
14584 KB |
ok, correct split |
7 |
Correct |
196 ms |
31732 KB |
ok, correct split |
8 |
Correct |
190 ms |
29816 KB |
ok, correct split |
9 |
Correct |
180 ms |
29300 KB |
ok, correct split |
10 |
Correct |
161 ms |
31988 KB |
ok, correct split |
11 |
Correct |
172 ms |
32116 KB |
ok, correct split |
12 |
Correct |
15 ms |
14584 KB |
ok, correct split |
13 |
Correct |
16 ms |
14584 KB |
ok, correct split |
14 |
Correct |
14 ms |
14584 KB |
ok, correct split |
15 |
Correct |
200 ms |
29628 KB |
ok, correct split |
16 |
Correct |
150 ms |
26080 KB |
ok, correct split |
17 |
Correct |
171 ms |
31964 KB |
ok, correct split |
18 |
Correct |
206 ms |
29680 KB |
ok, correct split |
19 |
Correct |
233 ms |
27768 KB |
ok, correct split |
20 |
Correct |
181 ms |
25780 KB |
ok, correct split |
21 |
Correct |
113 ms |
28784 KB |
ok, correct split |
22 |
Correct |
125 ms |
28656 KB |
ok, correct split |
23 |
Correct |
106 ms |
28656 KB |
ok, correct split |
24 |
Correct |
14 ms |
14584 KB |
ok, correct split |
25 |
Correct |
142 ms |
25976 KB |
ok, correct split |
26 |
Correct |
57 ms |
19084 KB |
ok, correct split |
27 |
Correct |
16 ms |
14584 KB |
ok, correct split |
28 |
Correct |
203 ms |
27768 KB |
ok, correct split |
29 |
Correct |
171 ms |
27768 KB |
ok, correct split |
30 |
Correct |
200 ms |
27512 KB |
ok, correct split |
31 |
Correct |
184 ms |
28512 KB |
ok, correct split |
32 |
Correct |
189 ms |
27384 KB |
ok, correct split |
33 |
Correct |
49 ms |
18296 KB |
ok, no valid answer |
34 |
Correct |
69 ms |
20216 KB |
ok, no valid answer |
35 |
Correct |
127 ms |
27384 KB |
ok, no valid answer |
36 |
Correct |
166 ms |
25848 KB |
ok, no valid answer |
37 |
Correct |
115 ms |
28272 KB |
ok, no valid answer |
38 |
Correct |
15 ms |
14584 KB |
ok, correct split |
39 |
Correct |
14 ms |
14584 KB |
ok, no valid answer |
40 |
Correct |
15 ms |
14584 KB |
ok, correct split |
41 |
Correct |
18 ms |
14584 KB |
ok, correct split |
42 |
Correct |
16 ms |
14584 KB |
ok, correct split |
43 |
Correct |
16 ms |
14584 KB |
ok, correct split |
44 |
Correct |
14 ms |
14584 KB |
ok, correct split |
45 |
Correct |
16 ms |
14584 KB |
ok, correct split |
46 |
Correct |
18 ms |
14968 KB |
ok, correct split |
47 |
Correct |
17 ms |
15000 KB |
ok, correct split |
48 |
Correct |
17 ms |
14712 KB |
ok, correct split |
49 |
Correct |
19 ms |
14968 KB |
ok, correct split |
50 |
Correct |
15 ms |
14584 KB |
ok, correct split |
51 |
Correct |
15 ms |
14584 KB |
ok, correct split |
52 |
Correct |
15 ms |
14584 KB |
ok, correct split |
53 |
Correct |
15 ms |
14584 KB |
ok, correct split |
54 |
Correct |
14 ms |
14584 KB |
ok, correct split |
55 |
Correct |
15 ms |
14584 KB |
ok, correct split |
56 |
Correct |
15 ms |
14712 KB |
ok, correct split |
57 |
Correct |
17 ms |
14712 KB |
ok, correct split |
58 |
Correct |
19 ms |
15020 KB |
ok, correct split |
59 |
Correct |
18 ms |
15096 KB |
ok, correct split |
60 |
Correct |
16 ms |
14968 KB |
ok, correct split |
61 |
Correct |
17 ms |
14968 KB |
ok, correct split |
62 |
Correct |
18 ms |
14968 KB |
ok, correct split |
63 |
Correct |
17 ms |
14968 KB |
ok, correct split |
64 |
Correct |
17 ms |
15096 KB |
ok, correct split |
65 |
Correct |
18 ms |
15096 KB |
ok, correct split |
66 |
Correct |
15 ms |
14712 KB |
ok, correct split |
67 |
Correct |
17 ms |
15100 KB |
ok, correct split |
68 |
Correct |
16 ms |
14712 KB |
ok, correct split |
69 |
Correct |
15 ms |
14712 KB |
ok, correct split |
70 |
Correct |
15 ms |
14712 KB |
ok, correct split |
71 |
Correct |
17 ms |
14972 KB |
ok, correct split |
72 |
Correct |
18 ms |
14968 KB |
ok, correct split |
73 |
Correct |
17 ms |
14968 KB |
ok, correct split |
74 |
Correct |
19 ms |
15096 KB |
ok, correct split |
75 |
Correct |
18 ms |
14968 KB |
ok, correct split |
76 |
Correct |
18 ms |
15096 KB |
ok, correct split |
77 |
Correct |
17 ms |
14968 KB |
ok, correct split |
78 |
Correct |
17 ms |
14840 KB |
ok, correct split |
79 |
Correct |
16 ms |
14840 KB |
ok, correct split |
80 |
Correct |
18 ms |
14968 KB |
ok, correct split |
81 |
Correct |
19 ms |
15096 KB |
ok, correct split |
82 |
Correct |
19 ms |
14972 KB |
ok, correct split |
83 |
Correct |
17 ms |
14968 KB |
ok, correct split |
84 |
Correct |
17 ms |
14968 KB |
ok, no valid answer |
85 |
Correct |
17 ms |
14968 KB |
ok, correct split |
86 |
Correct |
20 ms |
14968 KB |
ok, correct split |
87 |
Correct |
15 ms |
14584 KB |
ok, no valid answer |
88 |
Correct |
15 ms |
14584 KB |
ok, no valid answer |
89 |
Correct |
16 ms |
14968 KB |
ok, no valid answer |
90 |
Correct |
18 ms |
14968 KB |
ok, no valid answer |
91 |
Correct |
17 ms |
14968 KB |
ok, no valid answer |
92 |
Correct |
18 ms |
14968 KB |
ok, no valid answer |
93 |
Correct |
20 ms |
14968 KB |
ok, no valid answer |
94 |
Correct |
180 ms |
29424 KB |
ok, correct split |
95 |
Correct |
242 ms |
34032 KB |
ok, correct split |
96 |
Correct |
216 ms |
32500 KB |
ok, correct split |
97 |
Correct |
56 ms |
19576 KB |
ok, correct split |
98 |
Correct |
54 ms |
19704 KB |
ok, correct split |
99 |
Correct |
82 ms |
21556 KB |
ok, correct split |
100 |
Correct |
205 ms |
30584 KB |
ok, correct split |
101 |
Correct |
198 ms |
29432 KB |
ok, correct split |
102 |
Correct |
188 ms |
29808 KB |
ok, correct split |
103 |
Correct |
182 ms |
29808 KB |
ok, correct split |
104 |
Correct |
183 ms |
30732 KB |
ok, correct split |
105 |
Correct |
96 ms |
22524 KB |
ok, correct split |
106 |
Correct |
188 ms |
32872 KB |
ok, correct split |
107 |
Correct |
149 ms |
27128 KB |
ok, correct split |
108 |
Correct |
163 ms |
27000 KB |
ok, correct split |
109 |
Correct |
248 ms |
30072 KB |
ok, correct split |
110 |
Correct |
221 ms |
30064 KB |
ok, correct split |
111 |
Correct |
229 ms |
30064 KB |
ok, correct split |
112 |
Correct |
196 ms |
30320 KB |
ok, correct split |
113 |
Correct |
200 ms |
30192 KB |
ok, correct split |
114 |
Correct |
28 ms |
16504 KB |
ok, correct split |
115 |
Correct |
28 ms |
16368 KB |
ok, correct split |
116 |
Correct |
203 ms |
30064 KB |
ok, correct split |
117 |
Correct |
197 ms |
29808 KB |
ok, correct split |
118 |
Correct |
162 ms |
27124 KB |
ok, correct split |
119 |
Correct |
172 ms |
26976 KB |
ok, correct split |
120 |
Correct |
160 ms |
30196 KB |
ok, correct split |
121 |
Correct |
142 ms |
26744 KB |
ok, no valid answer |
122 |
Correct |
140 ms |
27260 KB |
ok, no valid answer |
123 |
Correct |
217 ms |
30368 KB |
ok, no valid answer |
124 |
Correct |
228 ms |
30244 KB |
ok, no valid answer |
125 |
Correct |
173 ms |
29680 KB |
ok, no valid answer |
126 |
Correct |
104 ms |
28144 KB |
ok, no valid answer |
127 |
Correct |
179 ms |
29428 KB |
ok, no valid answer |