#include "split.h"
#include <bits/stdc++.h>
using namespace std;
struct Fau {
int n;
vector<int> parent;
vector<vector<int>> bucket;
Fau(int n): n(n), parent(n), bucket(n) {
for (int i = 0; i < n; ++i) {
bucket[i].push_back(i);
parent[i] = i;
}
}
int Root(int a) {
return parent[a] == a ? a : Root(parent[a]);
}
int Union(int a, int b) {
a = Root(a);
b = Root(b);
if (a == b)
return a;
if (bucket[a].size() > bucket[b].size())
swap(a, b);
parent[a] = b;
bucket[b].insert(bucket[b].end(), bucket[a].begin(), bucket[a].end());
bucket[a].clear();
bucket[a].shrink_to_fit();
return b;
}
int Size(int v) {
return (int) bucket[v].size();
}
};
struct Solver {
int n, m;
vector<vector<pair<int, int>>> graph;
vector<int> tree_edges;
vector<int> used, sizes;
vector<pair<int, int>> component_sizes;
Solver(int n, const vector<pair<int, int>>& edges, int a, int b, int c)
: n(n), m(edges.size()), graph(n), tree_edges(m), used(n), sizes(n) {
component_sizes.emplace_back(a, 1);
component_sizes.emplace_back(b, 2);
component_sizes.emplace_back(c, 3);
sort(component_sizes.begin(), component_sizes.end());
for (int i = 0; i < m; ++i) {
int x = edges[i].first, y = edges[i].second;
graph[x].emplace_back(y, i);
graph[y].emplace_back(x, i);
}
}
void FindSpanningTree(int v) {
used[v] = 1;
sizes[v] = 1;
for (const auto& edge: graph[v]) {
int to = edge.first, id = edge.second;
if (used[to])
continue;
tree_edges[id] = 1;
FindSpanningTree(to);
sizes[v] += sizes[to];
}
}
int FindCentroid(int v, int parent) {
for (const auto& edge: graph[v]) {
int to = edge.first, id = edge.second;
if (to == parent || !tree_edges[id])
continue;
if (2 * sizes[to] > n)
return FindCentroid(to, v);
}
return v;
}
void UniteSubtrees(int centroid, Fau& fau) {
for (int i = 0; i < n; ++i) {
if (i == centroid)
continue;
for (const auto& edge: graph[i]) {
int to = edge.first, id = edge.second;
if (to == centroid || !tree_edges[id])
continue;
fau.Union(i, to);
}
}
}
vector<int> Solve() {
FindSpanningTree(0);
int centroid = FindCentroid(0, -1);
Fau fau(n);
UniteSubtrees(centroid, fau);
int max_subtree_vertex = -1, max_subtree_size = -1;
for (int i = 0; i < n; ++i) {
if (i == centroid)
continue;
if (fau.Root(i) == i && fau.Size(i) > max_subtree_size) {
max_subtree_size = fau.Size(i);
max_subtree_vertex = i;
}
}
for (int i = 0; i < n; ++i) {
if (i == centroid)
continue;
for (const auto& edge: graph[i]) {
if (max_subtree_size >= component_sizes[0].first)
break;
int to = edge.first;
if (to == centroid)
continue;
int vertex = fau.Union(i, to);
if (fau.Size(vertex) > max_subtree_size) {
max_subtree_size = fau.Size(vertex);
max_subtree_vertex = vertex;
}
}
}
// Solution was not found!
if (max_subtree_size < component_sizes[0].first) {
return vector<int>(n);
}
vector<int> result(n, component_sizes.back().second);
Color(max_subtree_vertex, fau.bucket[max_subtree_vertex], component_sizes[0].first, component_sizes[0].second, result);
Color(centroid, Complement(fau.bucket[max_subtree_vertex]), component_sizes[1].first, component_sizes[1].second, result);
return result;
}
void Color(int v, const vector<int>& allowed_vertices, int size, int color, vector<int>& colors) {
vector<int> used(n, 1);
for (int e: allowed_vertices)
used[e] = 0;
queue<int> q;
q.push(v);
used[v] = 1;
while (!q.empty() && size > 0) {
v = q.front();
q.pop();
colors[v] = color;
--size;
for (const auto& edge: graph[v]) {
int to = edge.first;
if (!used[to]) {
q.push(to);
used[to] = 1;
}
}
}
}
vector<int> Complement(const vector<int>& a) {
vector<int> b(n), result;
for (int e: a) b[e] = 1;
for (int i = 0; i < n; ++i) {
if (!b[i])
result.push_back(i);
}
return result;
}
};
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
int m = static_cast<int>(p.size());
vector<pair<int, int>> edges;
for (int i = 0; i < m; ++i) {
edges.emplace_back(p[i], q[i]);
}
Solver solver(n, edges, a, b, c);
return solver.Solve();
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
ok, correct split |
2 |
Correct |
2 ms |
376 KB |
ok, correct split |
3 |
Correct |
2 ms |
376 KB |
ok, correct split |
4 |
Correct |
2 ms |
376 KB |
ok, correct split |
5 |
Correct |
2 ms |
376 KB |
ok, correct split |
6 |
Correct |
2 ms |
376 KB |
ok, correct split |
7 |
Correct |
208 ms |
19900 KB |
ok, correct split |
8 |
Correct |
201 ms |
18924 KB |
ok, correct split |
9 |
Correct |
138 ms |
18540 KB |
ok, correct split |
10 |
Correct |
136 ms |
20076 KB |
ok, correct split |
11 |
Correct |
215 ms |
20076 KB |
ok, correct split |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
256 KB |
ok, correct split |
2 |
Correct |
2 ms |
256 KB |
ok, correct split |
3 |
Correct |
2 ms |
376 KB |
ok, correct split |
4 |
Correct |
243 ms |
20132 KB |
ok, correct split |
5 |
Correct |
155 ms |
16620 KB |
ok, correct split |
6 |
Correct |
147 ms |
19180 KB |
ok, correct split |
7 |
Correct |
158 ms |
17900 KB |
ok, correct split |
8 |
Correct |
206 ms |
21992 KB |
ok, correct split |
9 |
Correct |
141 ms |
15468 KB |
ok, correct split |
10 |
Correct |
83 ms |
17900 KB |
ok, correct split |
11 |
Correct |
85 ms |
18412 KB |
ok, correct split |
12 |
Correct |
89 ms |
18924 KB |
ok, correct split |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
ok, correct split |
2 |
Correct |
141 ms |
16780 KB |
ok, correct split |
3 |
Correct |
47 ms |
7664 KB |
ok, correct split |
4 |
Correct |
3 ms |
376 KB |
ok, correct split |
5 |
Correct |
175 ms |
16760 KB |
ok, correct split |
6 |
Correct |
137 ms |
16620 KB |
ok, correct split |
7 |
Correct |
148 ms |
16492 KB |
ok, correct split |
8 |
Correct |
163 ms |
17192 KB |
ok, correct split |
9 |
Correct |
147 ms |
16364 KB |
ok, correct split |
10 |
Correct |
42 ms |
5872 KB |
ok, no valid answer |
11 |
Correct |
72 ms |
8432 KB |
ok, no valid answer |
12 |
Correct |
112 ms |
16876 KB |
ok, no valid answer |
13 |
Correct |
135 ms |
17132 KB |
ok, no valid answer |
14 |
Correct |
77 ms |
16620 KB |
ok, no valid answer |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
256 KB |
ok, correct split |
2 |
Correct |
2 ms |
376 KB |
ok, no valid answer |
3 |
Correct |
2 ms |
376 KB |
ok, correct split |
4 |
Correct |
2 ms |
376 KB |
ok, correct split |
5 |
Correct |
2 ms |
380 KB |
ok, correct split |
6 |
Correct |
2 ms |
376 KB |
ok, correct split |
7 |
Correct |
2 ms |
256 KB |
ok, correct split |
8 |
Correct |
2 ms |
376 KB |
ok, correct split |
9 |
Correct |
5 ms |
888 KB |
ok, correct split |
10 |
Correct |
5 ms |
888 KB |
ok, correct split |
11 |
Correct |
2 ms |
376 KB |
ok, correct split |
12 |
Correct |
5 ms |
888 KB |
ok, correct split |
13 |
Correct |
2 ms |
312 KB |
ok, correct split |
14 |
Correct |
2 ms |
276 KB |
ok, correct split |
15 |
Correct |
2 ms |
376 KB |
ok, correct split |
16 |
Correct |
2 ms |
376 KB |
ok, correct split |
17 |
Correct |
2 ms |
376 KB |
ok, correct split |
18 |
Correct |
2 ms |
376 KB |
ok, correct split |
19 |
Correct |
3 ms |
376 KB |
ok, correct split |
20 |
Correct |
4 ms |
504 KB |
ok, correct split |
21 |
Correct |
5 ms |
760 KB |
ok, correct split |
22 |
Correct |
4 ms |
764 KB |
ok, correct split |
23 |
Correct |
4 ms |
760 KB |
ok, correct split |
24 |
Correct |
4 ms |
760 KB |
ok, correct split |
25 |
Correct |
4 ms |
760 KB |
ok, correct split |
26 |
Correct |
5 ms |
888 KB |
ok, correct split |
27 |
Correct |
5 ms |
892 KB |
ok, correct split |
28 |
Correct |
5 ms |
888 KB |
ok, correct split |
29 |
Correct |
2 ms |
376 KB |
ok, correct split |
30 |
Correct |
5 ms |
804 KB |
ok, correct split |
31 |
Correct |
3 ms |
504 KB |
ok, correct split |
32 |
Correct |
2 ms |
376 KB |
ok, correct split |
33 |
Correct |
2 ms |
376 KB |
ok, correct split |
34 |
Correct |
5 ms |
760 KB |
ok, correct split |
35 |
Correct |
4 ms |
888 KB |
ok, correct split |
36 |
Correct |
4 ms |
760 KB |
ok, correct split |
37 |
Correct |
5 ms |
888 KB |
ok, correct split |
38 |
Correct |
5 ms |
888 KB |
ok, correct split |
39 |
Correct |
5 ms |
888 KB |
ok, correct split |
40 |
Correct |
5 ms |
888 KB |
ok, correct split |
41 |
Correct |
4 ms |
508 KB |
ok, correct split |
42 |
Correct |
4 ms |
504 KB |
ok, correct split |
43 |
Correct |
5 ms |
888 KB |
ok, correct split |
44 |
Correct |
5 ms |
888 KB |
ok, correct split |
45 |
Correct |
5 ms |
888 KB |
ok, correct split |
46 |
Correct |
4 ms |
732 KB |
ok, correct split |
47 |
Correct |
4 ms |
760 KB |
ok, no valid answer |
48 |
Correct |
4 ms |
760 KB |
ok, correct split |
49 |
Correct |
5 ms |
760 KB |
ok, correct split |
50 |
Correct |
2 ms |
376 KB |
ok, no valid answer |
51 |
Correct |
2 ms |
376 KB |
ok, no valid answer |
52 |
Correct |
4 ms |
808 KB |
ok, no valid answer |
53 |
Correct |
6 ms |
888 KB |
ok, no valid answer |
54 |
Correct |
4 ms |
760 KB |
ok, no valid answer |
55 |
Correct |
5 ms |
760 KB |
ok, no valid answer |
56 |
Correct |
5 ms |
760 KB |
ok, no valid answer |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
ok, correct split |
2 |
Correct |
2 ms |
376 KB |
ok, correct split |
3 |
Correct |
2 ms |
376 KB |
ok, correct split |
4 |
Correct |
2 ms |
376 KB |
ok, correct split |
5 |
Correct |
2 ms |
376 KB |
ok, correct split |
6 |
Correct |
2 ms |
376 KB |
ok, correct split |
7 |
Correct |
208 ms |
19900 KB |
ok, correct split |
8 |
Correct |
201 ms |
18924 KB |
ok, correct split |
9 |
Correct |
138 ms |
18540 KB |
ok, correct split |
10 |
Correct |
136 ms |
20076 KB |
ok, correct split |
11 |
Correct |
215 ms |
20076 KB |
ok, correct split |
12 |
Correct |
2 ms |
256 KB |
ok, correct split |
13 |
Correct |
2 ms |
256 KB |
ok, correct split |
14 |
Correct |
2 ms |
376 KB |
ok, correct split |
15 |
Correct |
243 ms |
20132 KB |
ok, correct split |
16 |
Correct |
155 ms |
16620 KB |
ok, correct split |
17 |
Correct |
147 ms |
19180 KB |
ok, correct split |
18 |
Correct |
158 ms |
17900 KB |
ok, correct split |
19 |
Correct |
206 ms |
21992 KB |
ok, correct split |
20 |
Correct |
141 ms |
15468 KB |
ok, correct split |
21 |
Correct |
83 ms |
17900 KB |
ok, correct split |
22 |
Correct |
85 ms |
18412 KB |
ok, correct split |
23 |
Correct |
89 ms |
18924 KB |
ok, correct split |
24 |
Correct |
2 ms |
376 KB |
ok, correct split |
25 |
Correct |
141 ms |
16780 KB |
ok, correct split |
26 |
Correct |
47 ms |
7664 KB |
ok, correct split |
27 |
Correct |
3 ms |
376 KB |
ok, correct split |
28 |
Correct |
175 ms |
16760 KB |
ok, correct split |
29 |
Correct |
137 ms |
16620 KB |
ok, correct split |
30 |
Correct |
148 ms |
16492 KB |
ok, correct split |
31 |
Correct |
163 ms |
17192 KB |
ok, correct split |
32 |
Correct |
147 ms |
16364 KB |
ok, correct split |
33 |
Correct |
42 ms |
5872 KB |
ok, no valid answer |
34 |
Correct |
72 ms |
8432 KB |
ok, no valid answer |
35 |
Correct |
112 ms |
16876 KB |
ok, no valid answer |
36 |
Correct |
135 ms |
17132 KB |
ok, no valid answer |
37 |
Correct |
77 ms |
16620 KB |
ok, no valid answer |
38 |
Correct |
2 ms |
256 KB |
ok, correct split |
39 |
Correct |
2 ms |
376 KB |
ok, no valid answer |
40 |
Correct |
2 ms |
376 KB |
ok, correct split |
41 |
Correct |
2 ms |
376 KB |
ok, correct split |
42 |
Correct |
2 ms |
380 KB |
ok, correct split |
43 |
Correct |
2 ms |
376 KB |
ok, correct split |
44 |
Correct |
2 ms |
256 KB |
ok, correct split |
45 |
Correct |
2 ms |
376 KB |
ok, correct split |
46 |
Correct |
5 ms |
888 KB |
ok, correct split |
47 |
Correct |
5 ms |
888 KB |
ok, correct split |
48 |
Correct |
2 ms |
376 KB |
ok, correct split |
49 |
Correct |
5 ms |
888 KB |
ok, correct split |
50 |
Correct |
2 ms |
312 KB |
ok, correct split |
51 |
Correct |
2 ms |
276 KB |
ok, correct split |
52 |
Correct |
2 ms |
376 KB |
ok, correct split |
53 |
Correct |
2 ms |
376 KB |
ok, correct split |
54 |
Correct |
2 ms |
376 KB |
ok, correct split |
55 |
Correct |
2 ms |
376 KB |
ok, correct split |
56 |
Correct |
3 ms |
376 KB |
ok, correct split |
57 |
Correct |
4 ms |
504 KB |
ok, correct split |
58 |
Correct |
5 ms |
760 KB |
ok, correct split |
59 |
Correct |
4 ms |
764 KB |
ok, correct split |
60 |
Correct |
4 ms |
760 KB |
ok, correct split |
61 |
Correct |
4 ms |
760 KB |
ok, correct split |
62 |
Correct |
4 ms |
760 KB |
ok, correct split |
63 |
Correct |
5 ms |
888 KB |
ok, correct split |
64 |
Correct |
5 ms |
892 KB |
ok, correct split |
65 |
Correct |
5 ms |
888 KB |
ok, correct split |
66 |
Correct |
2 ms |
376 KB |
ok, correct split |
67 |
Correct |
5 ms |
804 KB |
ok, correct split |
68 |
Correct |
3 ms |
504 KB |
ok, correct split |
69 |
Correct |
2 ms |
376 KB |
ok, correct split |
70 |
Correct |
2 ms |
376 KB |
ok, correct split |
71 |
Correct |
5 ms |
760 KB |
ok, correct split |
72 |
Correct |
4 ms |
888 KB |
ok, correct split |
73 |
Correct |
4 ms |
760 KB |
ok, correct split |
74 |
Correct |
5 ms |
888 KB |
ok, correct split |
75 |
Correct |
5 ms |
888 KB |
ok, correct split |
76 |
Correct |
5 ms |
888 KB |
ok, correct split |
77 |
Correct |
5 ms |
888 KB |
ok, correct split |
78 |
Correct |
4 ms |
508 KB |
ok, correct split |
79 |
Correct |
4 ms |
504 KB |
ok, correct split |
80 |
Correct |
5 ms |
888 KB |
ok, correct split |
81 |
Correct |
5 ms |
888 KB |
ok, correct split |
82 |
Correct |
5 ms |
888 KB |
ok, correct split |
83 |
Correct |
4 ms |
732 KB |
ok, correct split |
84 |
Correct |
4 ms |
760 KB |
ok, no valid answer |
85 |
Correct |
4 ms |
760 KB |
ok, correct split |
86 |
Correct |
5 ms |
760 KB |
ok, correct split |
87 |
Correct |
2 ms |
376 KB |
ok, no valid answer |
88 |
Correct |
2 ms |
376 KB |
ok, no valid answer |
89 |
Correct |
4 ms |
808 KB |
ok, no valid answer |
90 |
Correct |
6 ms |
888 KB |
ok, no valid answer |
91 |
Correct |
4 ms |
760 KB |
ok, no valid answer |
92 |
Correct |
5 ms |
760 KB |
ok, no valid answer |
93 |
Correct |
5 ms |
760 KB |
ok, no valid answer |
94 |
Correct |
181 ms |
19404 KB |
ok, correct split |
95 |
Correct |
226 ms |
25192 KB |
ok, correct split |
96 |
Correct |
282 ms |
23016 KB |
ok, correct split |
97 |
Correct |
49 ms |
7536 KB |
ok, correct split |
98 |
Correct |
50 ms |
7920 KB |
ok, correct split |
99 |
Correct |
72 ms |
10092 KB |
ok, correct split |
100 |
Correct |
206 ms |
25164 KB |
ok, correct split |
101 |
Correct |
179 ms |
23276 KB |
ok, correct split |
102 |
Correct |
163 ms |
22140 KB |
ok, correct split |
103 |
Correct |
142 ms |
21480 KB |
ok, correct split |
104 |
Correct |
152 ms |
22796 KB |
ok, correct split |
105 |
Correct |
74 ms |
11756 KB |
ok, correct split |
106 |
Correct |
145 ms |
23372 KB |
ok, correct split |
107 |
Correct |
145 ms |
18528 KB |
ok, correct split |
108 |
Correct |
135 ms |
18540 KB |
ok, correct split |
109 |
Correct |
212 ms |
24172 KB |
ok, correct split |
110 |
Correct |
207 ms |
24708 KB |
ok, correct split |
111 |
Correct |
233 ms |
24304 KB |
ok, correct split |
112 |
Correct |
198 ms |
24168 KB |
ok, correct split |
113 |
Correct |
196 ms |
24180 KB |
ok, correct split |
114 |
Correct |
19 ms |
2804 KB |
ok, correct split |
115 |
Correct |
17 ms |
2552 KB |
ok, correct split |
116 |
Correct |
216 ms |
24524 KB |
ok, correct split |
117 |
Correct |
193 ms |
24004 KB |
ok, correct split |
118 |
Correct |
152 ms |
16492 KB |
ok, correct split |
119 |
Correct |
149 ms |
17596 KB |
ok, correct split |
120 |
Correct |
147 ms |
18440 KB |
ok, correct split |
121 |
Correct |
142 ms |
17332 KB |
ok, no valid answer |
122 |
Correct |
134 ms |
18028 KB |
ok, no valid answer |
123 |
Correct |
236 ms |
23224 KB |
ok, no valid answer |
124 |
Correct |
217 ms |
24044 KB |
ok, no valid answer |
125 |
Correct |
122 ms |
18924 KB |
ok, no valid answer |
126 |
Correct |
74 ms |
15852 KB |
ok, no valid answer |
127 |
Correct |
146 ms |
19568 KB |
ok, no valid answer |