#include "split.h"
#include <bits/stdc++.h>
using namespace std;
struct dsu {
vector<int> par, siz;
void init(int n) {
vector<int>().swap(par);
vector<int>().swap(siz);
par.resize(n);
siz.resize(n);
for(int i = 0; i < n; i++) {
par[i] = i;
siz[i] = 1;
}
}
int get(int x) {
if(x == par[x]) return x;
return par[x] = get(par[x]);
}
bool unite(int x, int y) {
x = get(x); y = get(y);
if(x == y) return false;
if(siz[x] > siz[y]) swap(x, y);
par[x] = y;
siz[y] += siz[x];
return true;
}
};
dsu uf;
vector<vector<int>> adj;
vector<int> an, sub;
int dfs(int n, int par = -1) {
if(adj.size() == 1 && par != -1) {
return sub[n] = 1;
}
int ans = 1;
for(int ch : adj[n]) {
if(ch == par) continue;
ans += dfs(ch, n);
}
return sub[n] = ans;
}
int tar, red = -1;
void dfs_red(int n, int par = -1) {
if(uf.get(n) != red) {
if(par == -1) {
while(true) {}
}
return;
}
if(an[n]) return;
if(!tar) return;
tar--;
an[n] = 4;
for(int ch : adj[n]) {
if(ch == par) continue;
dfs_red(ch, n);
}
}
void dfs_ans(int n, int par = -1) {
if(an[n]) return;
if(!tar) return;
tar--;
an[n] = 4;
for(int ch : adj[n]) {
if(ch == par) continue;
dfs_ans(ch, n);
}
}
int find_centroid(int n, int par = -1) {
if(par == -1) {
for(int ch : adj[n]) {
if(sub[ch] > sub.size()/2) return find_centroid(ch, n);
}
}
for(int ch : adj[n]) {
if(ch == par) continue;
if(sub[ch] > sub.size()/2) return find_centroid(ch, n);
}
return n;
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
int x = 1, y = 2, z = 3;
int m = p.size();
if(a > b) {
swap(a, b);
swap(x, y);
}
if(b > c) {
swap(b, c);
swap(y, z);
}
if(a > b) {
swap(a, b);
swap(x, y);
}
adj.resize(n);
sub.resize(n);
uf.init(n);
for(int i = 0; i < m; i++) {
if(uf.unite(p[i], q[i])) {
adj[p[i]].push_back(q[i]);
adj[q[i]].push_back(p[i]);
p[i] = q[i] = -1;
}
}
dfs(0);
int k = find_centroid(0);
dfs(k);
uf.init(n);
for(int i = 0; i < adj.size(); i++) {
for(int j : adj[i]) {
if(i != k && j != k) {
uf.unite(i, j);
}
}
}
for(int i = 0; i < n; i++) {
if(i == k) continue;
if(a <= uf.siz[uf.get(i)]) {
red = uf.get(i);
break;
}
}
for(int i = 0; i < m && (red == -1); i++) {
if(p[i] != -1 && p[i] != k && q[i] != k) {
uf.unite(p[i], q[i]);
adj[p[i]].push_back(q[i]);
adj[q[i]].push_back(p[i]);
if(a <= uf.siz[uf.get(p[i])]) {
red = uf.get(p[i]);
}
}
}
assert(uf.siz[k] == 1);
an.resize(n, 0);
if(red == -1) return an;
for(int i = 0; i < n; i++) {
if(uf.get(i) == red) {
tar = a;
dfs_red(i);
break;
}
if(i == n-1) {
assert(false);
}
}
for(int i = 0; i < n; i++) {
if(an[i] == 4) an[i] = x;
}
/*
cout << x << ' ' << y << ' ' << z << '\n';
cout << a << ' ' << b << ' ' << c << '\n';
for(int i = 0; i < n; i++) cout << an[i] << ' ';
cout << '\n';
for(int i = 0; i < n; i++) cout << uf.get(i) << ' ';
cout << '\n';
*/
tar = b;
dfs_ans(k);
assert(tar == 0);
for(int i = 0; i < n; i++) {
if(an[i] == 4) an[i] = y;
if(an[i] == 0) an[i] = z;
}
for(int i = 0; i < n; i++) {
if(an[i] == x) a--;
if(an[i] == y) b--;
if(an[i] == z) c--;
}
return an;
}
Compilation message
split.cpp: In function 'int find_centroid(int, int)':
split.cpp:82:24: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
82 | if(sub[ch] > sub.size()/2) return find_centroid(ch, n);
split.cpp:87:20: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
87 | if(sub[ch] > sub.size()/2) return find_centroid(ch, n);
split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:121:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
121 | for(int i = 0; i < adj.size(); i++) {
| ~~^~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
204 KB |
ok, correct split |
2 |
Correct |
0 ms |
204 KB |
ok, correct split |
3 |
Correct |
0 ms |
204 KB |
ok, correct split |
4 |
Correct |
0 ms |
204 KB |
ok, correct split |
5 |
Correct |
0 ms |
204 KB |
ok, correct split |
6 |
Correct |
1 ms |
204 KB |
ok, correct split |
7 |
Correct |
86 ms |
15140 KB |
ok, correct split |
8 |
Correct |
85 ms |
13464 KB |
ok, correct split |
9 |
Correct |
94 ms |
12836 KB |
ok, correct split |
10 |
Correct |
77 ms |
15296 KB |
ok, correct split |
11 |
Correct |
85 ms |
14388 KB |
ok, correct split |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
204 KB |
ok, correct split |
2 |
Correct |
0 ms |
204 KB |
ok, correct split |
3 |
Correct |
0 ms |
204 KB |
ok, correct split |
4 |
Correct |
102 ms |
10116 KB |
ok, correct split |
5 |
Correct |
68 ms |
9320 KB |
ok, correct split |
6 |
Correct |
78 ms |
15284 KB |
ok, correct split |
7 |
Correct |
81 ms |
13224 KB |
ok, correct split |
8 |
Correct |
96 ms |
10732 KB |
ok, correct split |
9 |
Correct |
71 ms |
9268 KB |
ok, correct split |
10 |
Correct |
50 ms |
9688 KB |
ok, correct split |
11 |
Correct |
53 ms |
9580 KB |
ok, correct split |
12 |
Correct |
50 ms |
9620 KB |
ok, correct split |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
204 KB |
ok, correct split |
2 |
Correct |
74 ms |
9328 KB |
ok, correct split |
3 |
Correct |
30 ms |
3896 KB |
ok, correct split |
4 |
Correct |
0 ms |
204 KB |
ok, correct split |
5 |
Correct |
97 ms |
13976 KB |
ok, correct split |
6 |
Correct |
86 ms |
12328 KB |
ok, correct split |
7 |
Correct |
80 ms |
12600 KB |
ok, correct split |
8 |
Correct |
121 ms |
12476 KB |
ok, correct split |
9 |
Correct |
83 ms |
12980 KB |
ok, correct split |
10 |
Correct |
22 ms |
3268 KB |
ok, no valid answer |
11 |
Correct |
33 ms |
4852 KB |
ok, no valid answer |
12 |
Correct |
57 ms |
9504 KB |
ok, no valid answer |
13 |
Correct |
67 ms |
9396 KB |
ok, no valid answer |
14 |
Correct |
47 ms |
9624 KB |
ok, no valid answer |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
204 KB |
ok, correct split |
2 |
Correct |
0 ms |
204 KB |
ok, no valid answer |
3 |
Correct |
0 ms |
204 KB |
ok, correct split |
4 |
Correct |
0 ms |
204 KB |
ok, correct split |
5 |
Correct |
0 ms |
204 KB |
ok, correct split |
6 |
Correct |
0 ms |
204 KB |
ok, correct split |
7 |
Correct |
0 ms |
204 KB |
ok, correct split |
8 |
Correct |
1 ms |
204 KB |
ok, correct split |
9 |
Correct |
2 ms |
460 KB |
ok, correct split |
10 |
Correct |
2 ms |
460 KB |
ok, correct split |
11 |
Correct |
1 ms |
204 KB |
ok, correct split |
12 |
Correct |
2 ms |
460 KB |
ok, correct split |
13 |
Correct |
0 ms |
296 KB |
ok, correct split |
14 |
Correct |
1 ms |
208 KB |
ok, correct split |
15 |
Correct |
0 ms |
208 KB |
ok, correct split |
16 |
Correct |
1 ms |
208 KB |
ok, correct split |
17 |
Correct |
1 ms |
208 KB |
ok, correct split |
18 |
Correct |
0 ms |
208 KB |
ok, correct split |
19 |
Correct |
1 ms |
336 KB |
ok, correct split |
20 |
Correct |
1 ms |
308 KB |
ok, correct split |
21 |
Correct |
2 ms |
540 KB |
ok, correct split |
22 |
Correct |
2 ms |
564 KB |
ok, correct split |
23 |
Correct |
2 ms |
596 KB |
ok, correct split |
24 |
Correct |
2 ms |
592 KB |
ok, correct split |
25 |
Correct |
2 ms |
592 KB |
ok, correct split |
26 |
Correct |
2 ms |
592 KB |
ok, correct split |
27 |
Correct |
2 ms |
592 KB |
ok, correct split |
28 |
Correct |
2 ms |
592 KB |
ok, correct split |
29 |
Correct |
0 ms |
208 KB |
ok, correct split |
30 |
Correct |
2 ms |
592 KB |
ok, correct split |
31 |
Correct |
1 ms |
336 KB |
ok, correct split |
32 |
Correct |
1 ms |
208 KB |
ok, correct split |
33 |
Correct |
1 ms |
208 KB |
ok, correct split |
34 |
Correct |
2 ms |
464 KB |
ok, correct split |
35 |
Correct |
2 ms |
464 KB |
ok, correct split |
36 |
Correct |
2 ms |
464 KB |
ok, correct split |
37 |
Correct |
2 ms |
592 KB |
ok, correct split |
38 |
Correct |
2 ms |
592 KB |
ok, correct split |
39 |
Correct |
2 ms |
592 KB |
ok, correct split |
40 |
Correct |
3 ms |
568 KB |
ok, correct split |
41 |
Correct |
1 ms |
336 KB |
ok, correct split |
42 |
Correct |
1 ms |
432 KB |
ok, correct split |
43 |
Correct |
2 ms |
592 KB |
ok, correct split |
44 |
Correct |
2 ms |
592 KB |
ok, correct split |
45 |
Correct |
2 ms |
592 KB |
ok, correct split |
46 |
Correct |
2 ms |
564 KB |
ok, correct split |
47 |
Correct |
2 ms |
592 KB |
ok, no valid answer |
48 |
Correct |
2 ms |
436 KB |
ok, correct split |
49 |
Correct |
2 ms |
592 KB |
ok, correct split |
50 |
Correct |
1 ms |
208 KB |
ok, no valid answer |
51 |
Correct |
0 ms |
296 KB |
ok, no valid answer |
52 |
Correct |
2 ms |
464 KB |
ok, no valid answer |
53 |
Correct |
3 ms |
592 KB |
ok, no valid answer |
54 |
Correct |
1 ms |
464 KB |
ok, no valid answer |
55 |
Correct |
2 ms |
464 KB |
ok, no valid answer |
56 |
Correct |
2 ms |
476 KB |
ok, no valid answer |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
204 KB |
ok, correct split |
2 |
Correct |
0 ms |
204 KB |
ok, correct split |
3 |
Correct |
0 ms |
204 KB |
ok, correct split |
4 |
Correct |
0 ms |
204 KB |
ok, correct split |
5 |
Correct |
0 ms |
204 KB |
ok, correct split |
6 |
Correct |
1 ms |
204 KB |
ok, correct split |
7 |
Correct |
86 ms |
15140 KB |
ok, correct split |
8 |
Correct |
85 ms |
13464 KB |
ok, correct split |
9 |
Correct |
94 ms |
12836 KB |
ok, correct split |
10 |
Correct |
77 ms |
15296 KB |
ok, correct split |
11 |
Correct |
85 ms |
14388 KB |
ok, correct split |
12 |
Correct |
0 ms |
204 KB |
ok, correct split |
13 |
Correct |
0 ms |
204 KB |
ok, correct split |
14 |
Correct |
0 ms |
204 KB |
ok, correct split |
15 |
Correct |
102 ms |
10116 KB |
ok, correct split |
16 |
Correct |
68 ms |
9320 KB |
ok, correct split |
17 |
Correct |
78 ms |
15284 KB |
ok, correct split |
18 |
Correct |
81 ms |
13224 KB |
ok, correct split |
19 |
Correct |
96 ms |
10732 KB |
ok, correct split |
20 |
Correct |
71 ms |
9268 KB |
ok, correct split |
21 |
Correct |
50 ms |
9688 KB |
ok, correct split |
22 |
Correct |
53 ms |
9580 KB |
ok, correct split |
23 |
Correct |
50 ms |
9620 KB |
ok, correct split |
24 |
Correct |
0 ms |
204 KB |
ok, correct split |
25 |
Correct |
74 ms |
9328 KB |
ok, correct split |
26 |
Correct |
30 ms |
3896 KB |
ok, correct split |
27 |
Correct |
0 ms |
204 KB |
ok, correct split |
28 |
Correct |
97 ms |
13976 KB |
ok, correct split |
29 |
Correct |
86 ms |
12328 KB |
ok, correct split |
30 |
Correct |
80 ms |
12600 KB |
ok, correct split |
31 |
Correct |
121 ms |
12476 KB |
ok, correct split |
32 |
Correct |
83 ms |
12980 KB |
ok, correct split |
33 |
Correct |
22 ms |
3268 KB |
ok, no valid answer |
34 |
Correct |
33 ms |
4852 KB |
ok, no valid answer |
35 |
Correct |
57 ms |
9504 KB |
ok, no valid answer |
36 |
Correct |
67 ms |
9396 KB |
ok, no valid answer |
37 |
Correct |
47 ms |
9624 KB |
ok, no valid answer |
38 |
Correct |
0 ms |
204 KB |
ok, correct split |
39 |
Correct |
0 ms |
204 KB |
ok, no valid answer |
40 |
Correct |
0 ms |
204 KB |
ok, correct split |
41 |
Correct |
0 ms |
204 KB |
ok, correct split |
42 |
Correct |
0 ms |
204 KB |
ok, correct split |
43 |
Correct |
0 ms |
204 KB |
ok, correct split |
44 |
Correct |
0 ms |
204 KB |
ok, correct split |
45 |
Correct |
1 ms |
204 KB |
ok, correct split |
46 |
Correct |
2 ms |
460 KB |
ok, correct split |
47 |
Correct |
2 ms |
460 KB |
ok, correct split |
48 |
Correct |
1 ms |
204 KB |
ok, correct split |
49 |
Correct |
2 ms |
460 KB |
ok, correct split |
50 |
Correct |
0 ms |
296 KB |
ok, correct split |
51 |
Correct |
1 ms |
208 KB |
ok, correct split |
52 |
Correct |
0 ms |
208 KB |
ok, correct split |
53 |
Correct |
1 ms |
208 KB |
ok, correct split |
54 |
Correct |
1 ms |
208 KB |
ok, correct split |
55 |
Correct |
0 ms |
208 KB |
ok, correct split |
56 |
Correct |
1 ms |
336 KB |
ok, correct split |
57 |
Correct |
1 ms |
308 KB |
ok, correct split |
58 |
Correct |
2 ms |
540 KB |
ok, correct split |
59 |
Correct |
2 ms |
564 KB |
ok, correct split |
60 |
Correct |
2 ms |
596 KB |
ok, correct split |
61 |
Correct |
2 ms |
592 KB |
ok, correct split |
62 |
Correct |
2 ms |
592 KB |
ok, correct split |
63 |
Correct |
2 ms |
592 KB |
ok, correct split |
64 |
Correct |
2 ms |
592 KB |
ok, correct split |
65 |
Correct |
2 ms |
592 KB |
ok, correct split |
66 |
Correct |
0 ms |
208 KB |
ok, correct split |
67 |
Correct |
2 ms |
592 KB |
ok, correct split |
68 |
Correct |
1 ms |
336 KB |
ok, correct split |
69 |
Correct |
1 ms |
208 KB |
ok, correct split |
70 |
Correct |
1 ms |
208 KB |
ok, correct split |
71 |
Correct |
2 ms |
464 KB |
ok, correct split |
72 |
Correct |
2 ms |
464 KB |
ok, correct split |
73 |
Correct |
2 ms |
464 KB |
ok, correct split |
74 |
Correct |
2 ms |
592 KB |
ok, correct split |
75 |
Correct |
2 ms |
592 KB |
ok, correct split |
76 |
Correct |
2 ms |
592 KB |
ok, correct split |
77 |
Correct |
3 ms |
568 KB |
ok, correct split |
78 |
Correct |
1 ms |
336 KB |
ok, correct split |
79 |
Correct |
1 ms |
432 KB |
ok, correct split |
80 |
Correct |
2 ms |
592 KB |
ok, correct split |
81 |
Correct |
2 ms |
592 KB |
ok, correct split |
82 |
Correct |
2 ms |
592 KB |
ok, correct split |
83 |
Correct |
2 ms |
564 KB |
ok, correct split |
84 |
Correct |
2 ms |
592 KB |
ok, no valid answer |
85 |
Correct |
2 ms |
436 KB |
ok, correct split |
86 |
Correct |
2 ms |
592 KB |
ok, correct split |
87 |
Correct |
1 ms |
208 KB |
ok, no valid answer |
88 |
Correct |
0 ms |
296 KB |
ok, no valid answer |
89 |
Correct |
2 ms |
464 KB |
ok, no valid answer |
90 |
Correct |
3 ms |
592 KB |
ok, no valid answer |
91 |
Correct |
1 ms |
464 KB |
ok, no valid answer |
92 |
Correct |
2 ms |
464 KB |
ok, no valid answer |
93 |
Correct |
2 ms |
476 KB |
ok, no valid answer |
94 |
Correct |
80 ms |
10988 KB |
ok, correct split |
95 |
Correct |
96 ms |
13140 KB |
ok, correct split |
96 |
Correct |
88 ms |
12348 KB |
ok, correct split |
97 |
Correct |
24 ms |
4332 KB |
ok, correct split |
98 |
Correct |
25 ms |
4456 KB |
ok, correct split |
99 |
Correct |
32 ms |
5104 KB |
ok, correct split |
100 |
Correct |
86 ms |
13228 KB |
ok, correct split |
101 |
Correct |
77 ms |
12344 KB |
ok, correct split |
102 |
Correct |
89 ms |
12496 KB |
ok, correct split |
103 |
Correct |
68 ms |
12272 KB |
ok, correct split |
104 |
Correct |
71 ms |
13732 KB |
ok, correct split |
105 |
Correct |
43 ms |
6604 KB |
ok, correct split |
106 |
Correct |
71 ms |
13468 KB |
ok, correct split |
107 |
Correct |
70 ms |
10552 KB |
ok, correct split |
108 |
Correct |
81 ms |
10632 KB |
ok, correct split |
109 |
Correct |
87 ms |
12856 KB |
ok, correct split |
110 |
Correct |
104 ms |
13364 KB |
ok, correct split |
111 |
Correct |
100 ms |
13572 KB |
ok, correct split |
112 |
Correct |
95 ms |
13620 KB |
ok, correct split |
113 |
Correct |
96 ms |
13620 KB |
ok, correct split |
114 |
Correct |
9 ms |
1720 KB |
ok, correct split |
115 |
Correct |
8 ms |
1540 KB |
ok, correct split |
116 |
Correct |
80 ms |
13328 KB |
ok, correct split |
117 |
Correct |
76 ms |
13296 KB |
ok, correct split |
118 |
Correct |
77 ms |
10608 KB |
ok, correct split |
119 |
Correct |
76 ms |
10528 KB |
ok, correct split |
120 |
Correct |
84 ms |
15588 KB |
ok, correct split |
121 |
Correct |
80 ms |
10560 KB |
ok, no valid answer |
122 |
Correct |
65 ms |
10604 KB |
ok, no valid answer |
123 |
Correct |
108 ms |
14384 KB |
ok, no valid answer |
124 |
Correct |
101 ms |
14372 KB |
ok, no valid answer |
125 |
Correct |
70 ms |
11640 KB |
ok, no valid answer |
126 |
Correct |
40 ms |
9744 KB |
ok, no valid answer |
127 |
Correct |
70 ms |
12052 KB |
ok, no valid answer |