#include<bits/stdc++.h>
#include "split.h"
using namespace std;
#define x first
#define y second
using ll = long long;
using vi = vector<int>;
using vl = vector<ll>;
using vb = vector<bool>;
using vii = vector<vi>;
using pi = pair<int, int>;
using vpi = vector<pi>;
const int MX = 2e5 + 100;
int N, M;
int A, B, C;
vpi visos;
vii edges(MX);
vii zemyn(MX);
unordered_set<int> inTree[MX];
vi col(3);
vi kiek(3);
vi sz(MX, 0);
vi res;
vb been(MX, false);
vi par(MX);
vi szp(MX, 1);
int findSet(int i) { return (i == par[i] ? i : (par[i] = findSet(par[i]))); }
bool isSameSet(int i, int j) { return findSet(i) == findSet(j); }
bool unionSet(int i, int j) {
if (isSameSet(i, j)) return false;
i = findSet(i);
j = findSet(j);
if (szp[i] > szp[j]) swap(i, j);
par[i] = j;
szp[j] += szp[i];
return true;
}
bool colored = false;
bool nepilnas = false;
void makeSz(int x) {
sz[x] = 1;
been[x] = true;
for (auto u : edges[x]) {
if (been[u]) continue;
inTree[x].insert(u);
inTree[u].insert(x);
// zemyn[x].emplace_back(u);
makeSz(u);
sz[x] += sz[u];
}
}
void makeZemyn(int x) {
been[x] = true;
for (auto u : edges[x]) {
if (been[u] or !inTree[x].count(u)) continue;
zemyn[x].emplace_back(u);
// printf("zemyn x -> u %d -> %d\n", x, u);
makeZemyn(u);
}
}
void color(int x, int p, int c) {
if (kiek[c] <= 0) return;
// printf("c = %d, x = %d, col = %d, kiek = %d\n", c, x, col[c], kiek[c]);
res[x] = col[c];
kiek[c]--;
if (kiek[c] <= 0) return;
for (auto u : edges[x])
if (u != p and res[u] == 0)
color(u, x, c);
}
void colorMult(int x, int c, int cent) {
if (kiek[c] <= 0) return;
res[x] = col[c];
kiek[c]--;
if (kiek[c] <= 0) return;
for (auto u : edges[x]) {
if (u == cent) continue;
if (inTree[x].count(u) == 0) continue;
if (res[u] != 0) continue;
colorMult(u, c, cent);
}
}
void colorZemyn(int x, int c) {
if (kiek[c] <= 0) return;
res[x] = col[c];
kiek[c]--;
if (kiek[c] <= 0) return;
for (auto u : zemyn[x])
colorZemyn(u, c);
}
void unite(int x) {
for (auto u : zemyn[x]) {
// printf("jungiu u = %d, x = %d\n", u, x);
unionSet(x, u);
unite(u);
}
}
void colorAll(int x, int c) {
been[x] = true;
if (kiek[c] <= 0) return;
// printf("c = %d, x = %d, col = %d, kiek = %d\n", c, x, col[c], kiek[c]);
res[x] = col[c];
kiek[c]--;
if (kiek[c] <= 0) return;
for (auto u : edges[x])
if (!been[u])
colorAll(u, c);
}
void solve(int x) {
// x is centroid
been = vb(N, false);
makeZemyn(x);
for (auto u : edges[x]) {
if (inTree[x].count(u) == 0) continue;
unite(u);
// printf("x = %d, u = %d, szu = %d, szp = %d\n", x, u, sz[u], szp[findSet(u)]);
assert(sz[u] == szp[findSet(u)]);
if (sz[u] >= kiek[0]) {
#ifdef LOCAL
printf("PIRMO x = %d, u = %d\n", x, u);
#endif
colorZemyn(u, 0);
color(x, u, 1);
return;
}
}
// reik jungt
for (auto u : visos) {
if (u.x == x or u.y == x) continue;
if (isSameSet(u.x, u.y)) continue;
inTree[u.x].insert(u.y);
inTree[u.y].insert(u.x);
unionSet(u.x, u.y);
if (szp[findSet(u.x)] >= kiek[0]) {
#ifdef LOCAL
printf("SUJUNGUS x = %d, u = %d %d\n", x, u.x, u.y);
#endif
colorMult(findSet(u.x), 0, x);
color(x, -1, 1);
return;
}
}
nepilnas = true;
}
void dfs(int x, int p) {
int centroid = 1;
for (auto u : edges[x]) {
if (sz[u] > N / 2)
centroid = 0;
}
if (centroid) {
colored = true;
solve(x);
return;
}
for (auto u : edges[x]) {
if (u == p or !inTree[x].count(u)) continue;
int prevX = sz[x];
int prevU = sz[u];
sz[x] -= sz[u];
sz[u] += sz[x];
dfs(u, x);
sz[x] = prevX;
sz[u] = prevU;
if (colored) return;
}
}
void sortabc() {
if (A >= B and A >= C) {
col[2] = 1;
kiek[2] = A;
col[1] = 2;
kiek[1] = B;
col[0] = 3;
kiek[0] = C;
} else if (B >= A and B >= C) {
col[2] = 2;
kiek[2] = B;
col[1] = 1;
kiek[1] = A;
col[0] = 3;
kiek[0] = C;
} else {
col[2] = 3;
kiek[2] = C;
col[1] = 2;
kiek[1] = B;
col[0] = 1;
kiek[0] = A;
}
if (kiek[0] > kiek[1]) {
swap(kiek[0], kiek[1]);
swap(col[0], col[1]);
}
}
vi find_split(int n, int a, int b, int c, vi p, vi q) {
res.resize(n, 0);
N = n;
A = a;
B = b;
C = c;
M = (int)p.size();
for (int i = 0; i < N; ++i)
par[i] = i;
for (int i = 0; i < M; ++i)
{
edges[p[i]].emplace_back(q[i]);
edges[q[i]].emplace_back(p[i]);
visos.emplace_back(p[i], q[i]);
}
sortabc();
// if (kiek[0] == 1) {
// been.resize(N, false);
// colorAll(0, 1);
// for (int i = 0; i < N; ++i)
// {
// if (!res[i]) {
// if (kiek[0]) {
// res[i] = col[0];
// kiek[0]--;
// } else {
// res[i] = col[2];
// }
// }
// }
// return res;
// }
been.resize(N, false);
makeSz(0);
been.resize(N, false);
dfs(0, -1);
// for (int i = 0; i < N; ++i)
// {
// printf("%d ", res[i]);
// }
// printf("\n");
// printf("col %d %d %d\n", col[0], col[1], col[2]);
if (colored and !nepilnas) {
for (int i = 0; i < N; ++i)
{
if (!res[i]) res[i] = col[2];
}
}
return res;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
23040 KB |
ok, correct split |
2 |
Correct |
16 ms |
23040 KB |
ok, correct split |
3 |
Correct |
16 ms |
23040 KB |
ok, correct split |
4 |
Correct |
16 ms |
23040 KB |
ok, correct split |
5 |
Correct |
17 ms |
23296 KB |
ok, correct split |
6 |
Correct |
16 ms |
23040 KB |
ok, correct split |
7 |
Correct |
224 ms |
50412 KB |
ok, correct split |
8 |
Correct |
212 ms |
47468 KB |
ok, correct split |
9 |
Correct |
228 ms |
46956 KB |
ok, correct split |
10 |
Correct |
225 ms |
51052 KB |
ok, correct split |
11 |
Correct |
235 ms |
51052 KB |
ok, correct split |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
23040 KB |
ok, correct split |
2 |
Correct |
16 ms |
23040 KB |
ok, correct split |
3 |
Correct |
17 ms |
23168 KB |
ok, correct split |
4 |
Correct |
252 ms |
48672 KB |
ok, correct split |
5 |
Correct |
193 ms |
41388 KB |
ok, correct split |
6 |
Correct |
216 ms |
50924 KB |
ok, correct split |
7 |
Correct |
215 ms |
47212 KB |
ok, correct split |
8 |
Correct |
262 ms |
44520 KB |
ok, correct split |
9 |
Correct |
200 ms |
42348 KB |
ok, correct split |
10 |
Correct |
165 ms |
41060 KB |
ok, correct split |
11 |
Correct |
164 ms |
41060 KB |
ok, correct split |
12 |
Correct |
174 ms |
41108 KB |
ok, correct split |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
17 ms |
23040 KB |
ok, correct split |
2 |
Correct |
209 ms |
41452 KB |
ok, correct split |
3 |
Correct |
73 ms |
30448 KB |
ok, correct split |
4 |
Correct |
17 ms |
23040 KB |
ok, correct split |
5 |
Correct |
208 ms |
44908 KB |
ok, correct split |
6 |
Correct |
201 ms |
44780 KB |
ok, correct split |
7 |
Correct |
212 ms |
45348 KB |
ok, correct split |
8 |
Correct |
208 ms |
45804 KB |
ok, correct split |
9 |
Correct |
210 ms |
45036 KB |
ok, correct split |
10 |
Correct |
66 ms |
29168 KB |
ok, no valid answer |
11 |
Correct |
96 ms |
32368 KB |
ok, no valid answer |
12 |
Correct |
204 ms |
41068 KB |
ok, no valid answer |
13 |
Correct |
238 ms |
41580 KB |
ok, no valid answer |
14 |
Correct |
176 ms |
41064 KB |
ok, no valid answer |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
17 ms |
23040 KB |
ok, correct split |
2 |
Correct |
17 ms |
23040 KB |
ok, no valid answer |
3 |
Correct |
18 ms |
23040 KB |
ok, correct split |
4 |
Correct |
16 ms |
23040 KB |
ok, correct split |
5 |
Correct |
16 ms |
23040 KB |
ok, correct split |
6 |
Correct |
18 ms |
23040 KB |
ok, correct split |
7 |
Correct |
16 ms |
23040 KB |
ok, correct split |
8 |
Correct |
16 ms |
23040 KB |
ok, correct split |
9 |
Correct |
21 ms |
23680 KB |
ok, correct split |
10 |
Correct |
21 ms |
23552 KB |
ok, correct split |
11 |
Correct |
17 ms |
23168 KB |
ok, correct split |
12 |
Correct |
20 ms |
23680 KB |
ok, correct split |
13 |
Correct |
17 ms |
23040 KB |
ok, correct split |
14 |
Correct |
16 ms |
23040 KB |
ok, correct split |
15 |
Correct |
17 ms |
23040 KB |
ok, correct split |
16 |
Correct |
17 ms |
23040 KB |
ok, correct split |
17 |
Correct |
16 ms |
23040 KB |
ok, correct split |
18 |
Correct |
17 ms |
23040 KB |
ok, correct split |
19 |
Correct |
18 ms |
23168 KB |
ok, correct split |
20 |
Correct |
18 ms |
23296 KB |
ok, correct split |
21 |
Correct |
20 ms |
23680 KB |
ok, correct split |
22 |
Correct |
20 ms |
23552 KB |
ok, correct split |
23 |
Correct |
19 ms |
23680 KB |
ok, correct split |
24 |
Correct |
19 ms |
23552 KB |
ok, correct split |
25 |
Correct |
19 ms |
23552 KB |
ok, correct split |
26 |
Correct |
20 ms |
23680 KB |
ok, correct split |
27 |
Correct |
20 ms |
23680 KB |
ok, correct split |
28 |
Correct |
20 ms |
23680 KB |
ok, correct split |
29 |
Correct |
17 ms |
23168 KB |
ok, correct split |
30 |
Correct |
21 ms |
23680 KB |
ok, correct split |
31 |
Correct |
17 ms |
23168 KB |
ok, correct split |
32 |
Correct |
17 ms |
23168 KB |
ok, correct split |
33 |
Correct |
17 ms |
23168 KB |
ok, correct split |
34 |
Correct |
20 ms |
23552 KB |
ok, correct split |
35 |
Correct |
20 ms |
23552 KB |
ok, correct split |
36 |
Correct |
20 ms |
23552 KB |
ok, correct split |
37 |
Correct |
21 ms |
23680 KB |
ok, correct split |
38 |
Correct |
21 ms |
23680 KB |
ok, correct split |
39 |
Correct |
21 ms |
23680 KB |
ok, correct split |
40 |
Correct |
20 ms |
23680 KB |
ok, correct split |
41 |
Correct |
18 ms |
23296 KB |
ok, correct split |
42 |
Correct |
18 ms |
23296 KB |
ok, correct split |
43 |
Correct |
21 ms |
23680 KB |
ok, correct split |
44 |
Correct |
20 ms |
23680 KB |
ok, correct split |
45 |
Correct |
20 ms |
23680 KB |
ok, correct split |
46 |
Correct |
19 ms |
23680 KB |
ok, correct split |
47 |
Correct |
20 ms |
23680 KB |
ok, no valid answer |
48 |
Correct |
20 ms |
23552 KB |
ok, correct split |
49 |
Correct |
20 ms |
23680 KB |
ok, correct split |
50 |
Correct |
17 ms |
23040 KB |
ok, no valid answer |
51 |
Correct |
16 ms |
23040 KB |
ok, no valid answer |
52 |
Correct |
19 ms |
23552 KB |
ok, no valid answer |
53 |
Correct |
21 ms |
23680 KB |
ok, no valid answer |
54 |
Correct |
19 ms |
23624 KB |
ok, no valid answer |
55 |
Correct |
20 ms |
23552 KB |
ok, no valid answer |
56 |
Correct |
19 ms |
23552 KB |
ok, no valid answer |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
23040 KB |
ok, correct split |
2 |
Correct |
16 ms |
23040 KB |
ok, correct split |
3 |
Correct |
16 ms |
23040 KB |
ok, correct split |
4 |
Correct |
16 ms |
23040 KB |
ok, correct split |
5 |
Correct |
17 ms |
23296 KB |
ok, correct split |
6 |
Correct |
16 ms |
23040 KB |
ok, correct split |
7 |
Correct |
224 ms |
50412 KB |
ok, correct split |
8 |
Correct |
212 ms |
47468 KB |
ok, correct split |
9 |
Correct |
228 ms |
46956 KB |
ok, correct split |
10 |
Correct |
225 ms |
51052 KB |
ok, correct split |
11 |
Correct |
235 ms |
51052 KB |
ok, correct split |
12 |
Correct |
18 ms |
23040 KB |
ok, correct split |
13 |
Correct |
16 ms |
23040 KB |
ok, correct split |
14 |
Correct |
17 ms |
23168 KB |
ok, correct split |
15 |
Correct |
252 ms |
48672 KB |
ok, correct split |
16 |
Correct |
193 ms |
41388 KB |
ok, correct split |
17 |
Correct |
216 ms |
50924 KB |
ok, correct split |
18 |
Correct |
215 ms |
47212 KB |
ok, correct split |
19 |
Correct |
262 ms |
44520 KB |
ok, correct split |
20 |
Correct |
200 ms |
42348 KB |
ok, correct split |
21 |
Correct |
165 ms |
41060 KB |
ok, correct split |
22 |
Correct |
164 ms |
41060 KB |
ok, correct split |
23 |
Correct |
174 ms |
41108 KB |
ok, correct split |
24 |
Correct |
17 ms |
23040 KB |
ok, correct split |
25 |
Correct |
209 ms |
41452 KB |
ok, correct split |
26 |
Correct |
73 ms |
30448 KB |
ok, correct split |
27 |
Correct |
17 ms |
23040 KB |
ok, correct split |
28 |
Correct |
208 ms |
44908 KB |
ok, correct split |
29 |
Correct |
201 ms |
44780 KB |
ok, correct split |
30 |
Correct |
212 ms |
45348 KB |
ok, correct split |
31 |
Correct |
208 ms |
45804 KB |
ok, correct split |
32 |
Correct |
210 ms |
45036 KB |
ok, correct split |
33 |
Correct |
66 ms |
29168 KB |
ok, no valid answer |
34 |
Correct |
96 ms |
32368 KB |
ok, no valid answer |
35 |
Correct |
204 ms |
41068 KB |
ok, no valid answer |
36 |
Correct |
238 ms |
41580 KB |
ok, no valid answer |
37 |
Correct |
176 ms |
41064 KB |
ok, no valid answer |
38 |
Correct |
17 ms |
23040 KB |
ok, correct split |
39 |
Correct |
17 ms |
23040 KB |
ok, no valid answer |
40 |
Correct |
18 ms |
23040 KB |
ok, correct split |
41 |
Correct |
16 ms |
23040 KB |
ok, correct split |
42 |
Correct |
16 ms |
23040 KB |
ok, correct split |
43 |
Correct |
18 ms |
23040 KB |
ok, correct split |
44 |
Correct |
16 ms |
23040 KB |
ok, correct split |
45 |
Correct |
16 ms |
23040 KB |
ok, correct split |
46 |
Correct |
21 ms |
23680 KB |
ok, correct split |
47 |
Correct |
21 ms |
23552 KB |
ok, correct split |
48 |
Correct |
17 ms |
23168 KB |
ok, correct split |
49 |
Correct |
20 ms |
23680 KB |
ok, correct split |
50 |
Correct |
17 ms |
23040 KB |
ok, correct split |
51 |
Correct |
16 ms |
23040 KB |
ok, correct split |
52 |
Correct |
17 ms |
23040 KB |
ok, correct split |
53 |
Correct |
17 ms |
23040 KB |
ok, correct split |
54 |
Correct |
16 ms |
23040 KB |
ok, correct split |
55 |
Correct |
17 ms |
23040 KB |
ok, correct split |
56 |
Correct |
18 ms |
23168 KB |
ok, correct split |
57 |
Correct |
18 ms |
23296 KB |
ok, correct split |
58 |
Correct |
20 ms |
23680 KB |
ok, correct split |
59 |
Correct |
20 ms |
23552 KB |
ok, correct split |
60 |
Correct |
19 ms |
23680 KB |
ok, correct split |
61 |
Correct |
19 ms |
23552 KB |
ok, correct split |
62 |
Correct |
19 ms |
23552 KB |
ok, correct split |
63 |
Correct |
20 ms |
23680 KB |
ok, correct split |
64 |
Correct |
20 ms |
23680 KB |
ok, correct split |
65 |
Correct |
20 ms |
23680 KB |
ok, correct split |
66 |
Correct |
17 ms |
23168 KB |
ok, correct split |
67 |
Correct |
21 ms |
23680 KB |
ok, correct split |
68 |
Correct |
17 ms |
23168 KB |
ok, correct split |
69 |
Correct |
17 ms |
23168 KB |
ok, correct split |
70 |
Correct |
17 ms |
23168 KB |
ok, correct split |
71 |
Correct |
20 ms |
23552 KB |
ok, correct split |
72 |
Correct |
20 ms |
23552 KB |
ok, correct split |
73 |
Correct |
20 ms |
23552 KB |
ok, correct split |
74 |
Correct |
21 ms |
23680 KB |
ok, correct split |
75 |
Correct |
21 ms |
23680 KB |
ok, correct split |
76 |
Correct |
21 ms |
23680 KB |
ok, correct split |
77 |
Correct |
20 ms |
23680 KB |
ok, correct split |
78 |
Correct |
18 ms |
23296 KB |
ok, correct split |
79 |
Correct |
18 ms |
23296 KB |
ok, correct split |
80 |
Correct |
21 ms |
23680 KB |
ok, correct split |
81 |
Correct |
20 ms |
23680 KB |
ok, correct split |
82 |
Correct |
20 ms |
23680 KB |
ok, correct split |
83 |
Correct |
19 ms |
23680 KB |
ok, correct split |
84 |
Correct |
20 ms |
23680 KB |
ok, no valid answer |
85 |
Correct |
20 ms |
23552 KB |
ok, correct split |
86 |
Correct |
20 ms |
23680 KB |
ok, correct split |
87 |
Correct |
17 ms |
23040 KB |
ok, no valid answer |
88 |
Correct |
16 ms |
23040 KB |
ok, no valid answer |
89 |
Correct |
19 ms |
23552 KB |
ok, no valid answer |
90 |
Correct |
21 ms |
23680 KB |
ok, no valid answer |
91 |
Correct |
19 ms |
23624 KB |
ok, no valid answer |
92 |
Correct |
20 ms |
23552 KB |
ok, no valid answer |
93 |
Correct |
19 ms |
23552 KB |
ok, no valid answer |
94 |
Correct |
239 ms |
46720 KB |
ok, correct split |
95 |
Correct |
303 ms |
53888 KB |
ok, correct split |
96 |
Correct |
264 ms |
51816 KB |
ok, correct split |
97 |
Correct |
78 ms |
30704 KB |
ok, correct split |
98 |
Correct |
79 ms |
30964 KB |
ok, correct split |
99 |
Correct |
95 ms |
33004 KB |
ok, correct split |
100 |
Correct |
265 ms |
47080 KB |
ok, correct split |
101 |
Correct |
236 ms |
45672 KB |
ok, correct split |
102 |
Correct |
267 ms |
45308 KB |
ok, correct split |
103 |
Correct |
248 ms |
44836 KB |
ok, correct split |
104 |
Correct |
269 ms |
46696 KB |
ok, correct split |
105 |
Correct |
138 ms |
34924 KB |
ok, correct split |
106 |
Correct |
292 ms |
48384 KB |
ok, correct split |
107 |
Correct |
215 ms |
42220 KB |
ok, correct split |
108 |
Correct |
214 ms |
42092 KB |
ok, correct split |
109 |
Correct |
277 ms |
46440 KB |
ok, correct split |
110 |
Correct |
284 ms |
46952 KB |
ok, correct split |
111 |
Correct |
311 ms |
47068 KB |
ok, correct split |
112 |
Correct |
300 ms |
46440 KB |
ok, correct split |
113 |
Correct |
300 ms |
46184 KB |
ok, correct split |
114 |
Correct |
36 ms |
25972 KB |
ok, correct split |
115 |
Correct |
34 ms |
25588 KB |
ok, correct split |
116 |
Correct |
262 ms |
46936 KB |
ok, correct split |
117 |
Correct |
281 ms |
46936 KB |
ok, correct split |
118 |
Correct |
222 ms |
43244 KB |
ok, correct split |
119 |
Correct |
218 ms |
43116 KB |
ok, correct split |
120 |
Correct |
214 ms |
47340 KB |
ok, correct split |
121 |
Correct |
209 ms |
42092 KB |
ok, no valid answer |
122 |
Correct |
217 ms |
42348 KB |
ok, no valid answer |
123 |
Correct |
269 ms |
47336 KB |
ok, no valid answer |
124 |
Correct |
267 ms |
47208 KB |
ok, no valid answer |
125 |
Correct |
237 ms |
43756 KB |
ok, no valid answer |
126 |
Correct |
163 ms |
40044 KB |
ok, no valid answer |
127 |
Correct |
258 ms |
44264 KB |
ok, no valid answer |