#include <bits/stdc++.h>
#include "split.h"
#define all(x) x.begin(),x.end()
#define PB push_back
#define sz(x) ((int)x.size())
using namespace std;
typedef long long ll;
const int N = 100100;
vector<int> res;
vector<int> g[N], vc, children[N];
bool mrk[N];
int A[3], C[3], mrk_col[N], h[N], mn_h[N], pr[N], siz[N], mem = 0, mkk[N], tt = 0;
void dfs(int v, int p){
pr[v] = p;
siz[v] = 1;
mrk[v] = 1;
mn_h[v] = h[v];
for (int u : g[v]){
if (u == p) continue;
if (!mrk[u]) {
children[v].PB(u);
h[u] = h[v] + 1;
dfs(u, v);
mn_h[v] = min(mn_h[v], mn_h[u]);
siz[v] += siz[u];
} else mn_h[v] = min(mn_h[v], h[u]);
}
}
void col(int v, int cl){
mrk_col[v] = cl;
for (int u : children[v])
col(u, cl);
}
void DFS(int v, int cl, int rlc){
if (mrk[v]) return;
if (mem == 0) return;
mem--;
mrk[v] = 1;
res[v] = rlc;
for (int u : g[v])
if (mrk_col[u] == cl)
DFS(u, cl, rlc);
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
res.resize(n);
fill(all(res), 0);
for (int i = sz(p) - 1; i >= 0; i--){
g[p[i]].PB(q[i]);
g[q[i]].PB(p[i]);
}
A[0] = a; A[1] = b; A[2] = c;
C[0] = 1; C[1] = 2; C[2] = 3;
if (A[0] > A[1]) {
swap(A[0], A[1]);
swap(C[0], C[1]);
}
if (A[1] > A[2]) {
swap(A[1], A[2]);
swap(C[1], C[2]);
}
if (A[0] > A[1]) {
swap(A[0], A[1]);
swap(C[0], C[1]);
}
dfs(0, -1);
for (int v = 0; v < n; v++){
bool ok = bool(siz[v] >= A[0]);
for (int u : children[v])
ok &= bool(siz[u] < A[0]);
if (!ok) continue;
tt++;
int real_siz = siz[v];
for (int u : children[v])
if (mn_h[u] < h[v] && real_siz - siz[u] >= A[0]){
real_siz -= siz[u];
mkk[u] = tt;
}
for (int t1 = 0; t1 < 2; t1++){
int t2 = 1 - t1;
col(0, 1);
col(v, 2);
for (int u : children[v])
if (mkk[u] == tt)
col(u, 1);
if (real_siz >= A[t1] && n - real_siz >= A[t2]){
fill(mrk, mrk + n, 0);
mem = A[t2];
DFS(pr[v], 1, C[t2]);
mem = A[t1];
DFS(v, 2, C[t1]);
for (int &cr : res)
if (cr == 0)
cr = C[2];
return res;
}
}
}
return res;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
4992 KB |
ok, correct split |
2 |
Correct |
8 ms |
4992 KB |
ok, correct split |
3 |
Correct |
8 ms |
4992 KB |
ok, correct split |
4 |
Correct |
7 ms |
4992 KB |
ok, correct split |
5 |
Correct |
8 ms |
5120 KB |
ok, correct split |
6 |
Correct |
10 ms |
5120 KB |
ok, correct split |
7 |
Correct |
139 ms |
25848 KB |
ok, correct split |
8 |
Correct |
122 ms |
23032 KB |
ok, correct split |
9 |
Correct |
135 ms |
22264 KB |
ok, correct split |
10 |
Correct |
125 ms |
26232 KB |
ok, correct split |
11 |
Correct |
153 ms |
26232 KB |
ok, correct split |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
5120 KB |
ok, correct split |
2 |
Correct |
8 ms |
4992 KB |
ok, correct split |
3 |
Correct |
8 ms |
4992 KB |
ok, correct split |
4 |
Correct |
151 ms |
21752 KB |
ok, correct split |
5 |
Correct |
111 ms |
15480 KB |
ok, correct split |
6 |
Correct |
146 ms |
26232 KB |
ok, correct split |
7 |
Correct |
150 ms |
22776 KB |
ok, correct split |
8 |
Correct |
155 ms |
19168 KB |
ok, correct split |
9 |
Correct |
109 ms |
17016 KB |
ok, correct split |
10 |
Correct |
66 ms |
14320 KB |
ok, correct split |
11 |
Correct |
66 ms |
14192 KB |
ok, correct split |
12 |
Correct |
75 ms |
14576 KB |
ok, correct split |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
4992 KB |
ok, correct split |
2 |
Correct |
120 ms |
15480 KB |
ok, correct split |
3 |
Correct |
36 ms |
9216 KB |
ok, correct split |
4 |
Correct |
7 ms |
4992 KB |
ok, correct split |
5 |
Correct |
131 ms |
19960 KB |
ok, correct split |
6 |
Correct |
113 ms |
19704 KB |
ok, correct split |
7 |
Correct |
141 ms |
19448 KB |
ok, correct split |
8 |
Correct |
135 ms |
21112 KB |
ok, correct split |
9 |
Correct |
140 ms |
19320 KB |
ok, correct split |
10 |
Correct |
33 ms |
8576 KB |
ok, no valid answer |
11 |
Correct |
47 ms |
10240 KB |
ok, no valid answer |
12 |
Correct |
79 ms |
14836 KB |
ok, no valid answer |
13 |
Correct |
119 ms |
15352 KB |
ok, no valid answer |
14 |
Correct |
69 ms |
14576 KB |
ok, no valid answer |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
5120 KB |
ok, correct split |
2 |
Correct |
7 ms |
4992 KB |
ok, no valid answer |
3 |
Correct |
7 ms |
5120 KB |
ok, correct split |
4 |
Correct |
8 ms |
4992 KB |
ok, correct split |
5 |
Correct |
9 ms |
5092 KB |
ok, correct split |
6 |
Correct |
8 ms |
4992 KB |
ok, correct split |
7 |
Correct |
7 ms |
5120 KB |
ok, correct split |
8 |
Correct |
7 ms |
4992 KB |
ok, correct split |
9 |
Correct |
10 ms |
5504 KB |
ok, correct split |
10 |
Correct |
10 ms |
5376 KB |
ok, correct split |
11 |
Correct |
7 ms |
5120 KB |
ok, correct split |
12 |
Correct |
10 ms |
5376 KB |
ok, correct split |
13 |
Correct |
8 ms |
5120 KB |
ok, correct split |
14 |
Correct |
8 ms |
4992 KB |
ok, correct split |
15 |
Correct |
7 ms |
5120 KB |
ok, correct split |
16 |
Correct |
7 ms |
5120 KB |
ok, correct split |
17 |
Correct |
7 ms |
4992 KB |
ok, correct split |
18 |
Correct |
7 ms |
4992 KB |
ok, correct split |
19 |
Correct |
7 ms |
5120 KB |
ok, correct split |
20 |
Correct |
8 ms |
5248 KB |
ok, correct split |
21 |
Correct |
9 ms |
5376 KB |
ok, correct split |
22 |
Correct |
9 ms |
5376 KB |
ok, correct split |
23 |
Correct |
9 ms |
5504 KB |
ok, correct split |
24 |
Correct |
10 ms |
5480 KB |
ok, correct split |
25 |
Correct |
9 ms |
5376 KB |
ok, correct split |
26 |
Correct |
9 ms |
5376 KB |
ok, correct split |
27 |
Correct |
9 ms |
5376 KB |
ok, correct split |
28 |
Correct |
9 ms |
5376 KB |
ok, correct split |
29 |
Correct |
8 ms |
5120 KB |
ok, correct split |
30 |
Correct |
9 ms |
5376 KB |
ok, correct split |
31 |
Correct |
8 ms |
5120 KB |
ok, correct split |
32 |
Correct |
7 ms |
5120 KB |
ok, correct split |
33 |
Correct |
7 ms |
5120 KB |
ok, correct split |
34 |
Correct |
9 ms |
5376 KB |
ok, correct split |
35 |
Correct |
10 ms |
5376 KB |
ok, correct split |
36 |
Correct |
9 ms |
5376 KB |
ok, correct split |
37 |
Correct |
10 ms |
5376 KB |
ok, correct split |
38 |
Correct |
10 ms |
5504 KB |
ok, correct split |
39 |
Correct |
10 ms |
5376 KB |
ok, correct split |
40 |
Correct |
10 ms |
5376 KB |
ok, correct split |
41 |
Correct |
9 ms |
5248 KB |
ok, correct split |
42 |
Correct |
9 ms |
5248 KB |
ok, correct split |
43 |
Correct |
10 ms |
5376 KB |
ok, correct split |
44 |
Correct |
10 ms |
5504 KB |
ok, correct split |
45 |
Correct |
10 ms |
5504 KB |
ok, correct split |
46 |
Correct |
9 ms |
5504 KB |
ok, correct split |
47 |
Correct |
9 ms |
5376 KB |
ok, no valid answer |
48 |
Correct |
9 ms |
5376 KB |
ok, correct split |
49 |
Correct |
9 ms |
5376 KB |
ok, correct split |
50 |
Correct |
7 ms |
4992 KB |
ok, no valid answer |
51 |
Correct |
7 ms |
4992 KB |
ok, no valid answer |
52 |
Correct |
9 ms |
5248 KB |
ok, no valid answer |
53 |
Correct |
10 ms |
5376 KB |
ok, no valid answer |
54 |
Correct |
8 ms |
5248 KB |
ok, no valid answer |
55 |
Correct |
9 ms |
5376 KB |
ok, no valid answer |
56 |
Correct |
10 ms |
5376 KB |
ok, no valid answer |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
4992 KB |
ok, correct split |
2 |
Correct |
8 ms |
4992 KB |
ok, correct split |
3 |
Correct |
8 ms |
4992 KB |
ok, correct split |
4 |
Correct |
7 ms |
4992 KB |
ok, correct split |
5 |
Correct |
8 ms |
5120 KB |
ok, correct split |
6 |
Correct |
10 ms |
5120 KB |
ok, correct split |
7 |
Correct |
139 ms |
25848 KB |
ok, correct split |
8 |
Correct |
122 ms |
23032 KB |
ok, correct split |
9 |
Correct |
135 ms |
22264 KB |
ok, correct split |
10 |
Correct |
125 ms |
26232 KB |
ok, correct split |
11 |
Correct |
153 ms |
26232 KB |
ok, correct split |
12 |
Correct |
8 ms |
5120 KB |
ok, correct split |
13 |
Correct |
8 ms |
4992 KB |
ok, correct split |
14 |
Correct |
8 ms |
4992 KB |
ok, correct split |
15 |
Correct |
151 ms |
21752 KB |
ok, correct split |
16 |
Correct |
111 ms |
15480 KB |
ok, correct split |
17 |
Correct |
146 ms |
26232 KB |
ok, correct split |
18 |
Correct |
150 ms |
22776 KB |
ok, correct split |
19 |
Correct |
155 ms |
19168 KB |
ok, correct split |
20 |
Correct |
109 ms |
17016 KB |
ok, correct split |
21 |
Correct |
66 ms |
14320 KB |
ok, correct split |
22 |
Correct |
66 ms |
14192 KB |
ok, correct split |
23 |
Correct |
75 ms |
14576 KB |
ok, correct split |
24 |
Correct |
7 ms |
4992 KB |
ok, correct split |
25 |
Correct |
120 ms |
15480 KB |
ok, correct split |
26 |
Correct |
36 ms |
9216 KB |
ok, correct split |
27 |
Correct |
7 ms |
4992 KB |
ok, correct split |
28 |
Correct |
131 ms |
19960 KB |
ok, correct split |
29 |
Correct |
113 ms |
19704 KB |
ok, correct split |
30 |
Correct |
141 ms |
19448 KB |
ok, correct split |
31 |
Correct |
135 ms |
21112 KB |
ok, correct split |
32 |
Correct |
140 ms |
19320 KB |
ok, correct split |
33 |
Correct |
33 ms |
8576 KB |
ok, no valid answer |
34 |
Correct |
47 ms |
10240 KB |
ok, no valid answer |
35 |
Correct |
79 ms |
14836 KB |
ok, no valid answer |
36 |
Correct |
119 ms |
15352 KB |
ok, no valid answer |
37 |
Correct |
69 ms |
14576 KB |
ok, no valid answer |
38 |
Correct |
8 ms |
5120 KB |
ok, correct split |
39 |
Correct |
7 ms |
4992 KB |
ok, no valid answer |
40 |
Correct |
7 ms |
5120 KB |
ok, correct split |
41 |
Correct |
8 ms |
4992 KB |
ok, correct split |
42 |
Correct |
9 ms |
5092 KB |
ok, correct split |
43 |
Correct |
8 ms |
4992 KB |
ok, correct split |
44 |
Correct |
7 ms |
5120 KB |
ok, correct split |
45 |
Correct |
7 ms |
4992 KB |
ok, correct split |
46 |
Correct |
10 ms |
5504 KB |
ok, correct split |
47 |
Correct |
10 ms |
5376 KB |
ok, correct split |
48 |
Correct |
7 ms |
5120 KB |
ok, correct split |
49 |
Correct |
10 ms |
5376 KB |
ok, correct split |
50 |
Correct |
8 ms |
5120 KB |
ok, correct split |
51 |
Correct |
8 ms |
4992 KB |
ok, correct split |
52 |
Correct |
7 ms |
5120 KB |
ok, correct split |
53 |
Correct |
7 ms |
5120 KB |
ok, correct split |
54 |
Correct |
7 ms |
4992 KB |
ok, correct split |
55 |
Correct |
7 ms |
4992 KB |
ok, correct split |
56 |
Correct |
7 ms |
5120 KB |
ok, correct split |
57 |
Correct |
8 ms |
5248 KB |
ok, correct split |
58 |
Correct |
9 ms |
5376 KB |
ok, correct split |
59 |
Correct |
9 ms |
5376 KB |
ok, correct split |
60 |
Correct |
9 ms |
5504 KB |
ok, correct split |
61 |
Correct |
10 ms |
5480 KB |
ok, correct split |
62 |
Correct |
9 ms |
5376 KB |
ok, correct split |
63 |
Correct |
9 ms |
5376 KB |
ok, correct split |
64 |
Correct |
9 ms |
5376 KB |
ok, correct split |
65 |
Correct |
9 ms |
5376 KB |
ok, correct split |
66 |
Correct |
8 ms |
5120 KB |
ok, correct split |
67 |
Correct |
9 ms |
5376 KB |
ok, correct split |
68 |
Correct |
8 ms |
5120 KB |
ok, correct split |
69 |
Correct |
7 ms |
5120 KB |
ok, correct split |
70 |
Correct |
7 ms |
5120 KB |
ok, correct split |
71 |
Correct |
9 ms |
5376 KB |
ok, correct split |
72 |
Correct |
10 ms |
5376 KB |
ok, correct split |
73 |
Correct |
9 ms |
5376 KB |
ok, correct split |
74 |
Correct |
10 ms |
5376 KB |
ok, correct split |
75 |
Correct |
10 ms |
5504 KB |
ok, correct split |
76 |
Correct |
10 ms |
5376 KB |
ok, correct split |
77 |
Correct |
10 ms |
5376 KB |
ok, correct split |
78 |
Correct |
9 ms |
5248 KB |
ok, correct split |
79 |
Correct |
9 ms |
5248 KB |
ok, correct split |
80 |
Correct |
10 ms |
5376 KB |
ok, correct split |
81 |
Correct |
10 ms |
5504 KB |
ok, correct split |
82 |
Correct |
10 ms |
5504 KB |
ok, correct split |
83 |
Correct |
9 ms |
5504 KB |
ok, correct split |
84 |
Correct |
9 ms |
5376 KB |
ok, no valid answer |
85 |
Correct |
9 ms |
5376 KB |
ok, correct split |
86 |
Correct |
9 ms |
5376 KB |
ok, correct split |
87 |
Correct |
7 ms |
4992 KB |
ok, no valid answer |
88 |
Correct |
7 ms |
4992 KB |
ok, no valid answer |
89 |
Correct |
9 ms |
5248 KB |
ok, no valid answer |
90 |
Correct |
10 ms |
5376 KB |
ok, no valid answer |
91 |
Correct |
8 ms |
5248 KB |
ok, no valid answer |
92 |
Correct |
9 ms |
5376 KB |
ok, no valid answer |
93 |
Correct |
10 ms |
5376 KB |
ok, no valid answer |
94 |
Correct |
129 ms |
19100 KB |
ok, correct split |
95 |
Correct |
169 ms |
25080 KB |
ok, correct split |
96 |
Correct |
176 ms |
23416 KB |
ok, correct split |
97 |
Correct |
37 ms |
9180 KB |
ok, correct split |
98 |
Correct |
40 ms |
9464 KB |
ok, correct split |
99 |
Correct |
61 ms |
12152 KB |
ok, correct split |
100 |
Correct |
159 ms |
19936 KB |
ok, correct split |
101 |
Correct |
135 ms |
18680 KB |
ok, correct split |
102 |
Correct |
125 ms |
17908 KB |
ok, correct split |
103 |
Correct |
133 ms |
17728 KB |
ok, correct split |
104 |
Correct |
116 ms |
17888 KB |
ok, correct split |
105 |
Correct |
63 ms |
11768 KB |
ok, correct split |
106 |
Correct |
112 ms |
18024 KB |
ok, correct split |
107 |
Correct |
108 ms |
15864 KB |
ok, correct split |
108 |
Correct |
103 ms |
15608 KB |
ok, correct split |
109 |
Correct |
158 ms |
19448 KB |
ok, correct split |
110 |
Correct |
153 ms |
20420 KB |
ok, correct split |
111 |
Correct |
156 ms |
20208 KB |
ok, correct split |
112 |
Correct |
161 ms |
19168 KB |
ok, correct split |
113 |
Correct |
149 ms |
18800 KB |
ok, correct split |
114 |
Correct |
20 ms |
6912 KB |
ok, correct split |
115 |
Correct |
18 ms |
6528 KB |
ok, correct split |
116 |
Correct |
148 ms |
20592 KB |
ok, correct split |
117 |
Correct |
142 ms |
20208 KB |
ok, correct split |
118 |
Correct |
110 ms |
17016 KB |
ok, correct split |
119 |
Correct |
109 ms |
17016 KB |
ok, correct split |
120 |
Correct |
114 ms |
21240 KB |
ok, correct split |
121 |
Correct |
102 ms |
15480 KB |
ok, no valid answer |
122 |
Correct |
98 ms |
15352 KB |
ok, no valid answer |
123 |
Correct |
159 ms |
20088 KB |
ok, no valid answer |
124 |
Correct |
156 ms |
19832 KB |
ok, no valid answer |
125 |
Correct |
91 ms |
16400 KB |
ok, no valid answer |
126 |
Correct |
58 ms |
13680 KB |
ok, no valid answer |
127 |
Correct |
108 ms |
17280 KB |
ok, no valid answer |