#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
using namespace std;
using ll = long long;
#define sz(x) (int)(x).size()
using pii = pair<int,int>;
using tii = tuple<int,int,int>;
const int nmax = 1e5 + 5;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int n;
vector<int> leg[nmax];
struct Tree {
vector<int> g[nmax];
int root;
void clear() {
for(int i = 0; i < n; i++)
g[i].clear();
return;
}
void addedge(int a, int b) {
g[a].emplace_back(b);
g[b].emplace_back(a);
}
vector<int> togive;
int mxarea[nmax], area[nmax], p[nmax];
void down(int node, int f) {
p[node] = f;
for(auto x : g[node]) {
if(x == f) continue;
down(x, node);
area[node] += area[x];
mxarea[node] = max(mxarea[node], area[x]);
}
area[node]++;
}
void init() { togive.resize(n, 0); down(root, root); }
void fillgreedy(int node, int f, int& a) {
if(a == 0) return;
sort(all(g[node]), [&](int x, int b) { return area[x] < area[b] || (area[x] > a && area[b] > a && mxarea[x] < mxarea[b]); });
togive[node] = 1;
a--;
for(auto x : g[node]) {
if(x == f) continue;
fillgreedy(x, node, a);
if(a == 0) return;
}
}
vector<int> getbydown(int a) {
std::fill(all(togive), 0);
int best = root;
for(int i = 0; i < n; i++)
if(area[i] >= a && area[best] > area[i]) best = i;
fillgreedy(best, p[best], a);
return togive;
}
vector<int> getbyroot(int a) {
std::fill(all(togive), 0);
fillgreedy(root, root, a);
return togive;
}
int flag = 2;
int fill(int node, vector<int>& occ, int& b) {
if(b == 0) return 0;
if(occ[node] != 0) return 0;
occ[node] = flag;
int sum = 1;
b--;
for(auto x : leg[node])
sum += fill(x, occ, b);
return sum;
}
void fill(vector<int> &occ, int b) {
for(int i = 0; i < n; i++) {
if(occ[i] == 0) {
flag++;
int tmp = b;
fill(i, occ, b);
if(b == 0) {
//for(auto x : occ)
//cerr << x << ' ';
//cerr << '\n';
//cerr << flag << '\n';
for(auto &x : occ) {
if(x == 1) continue;
if(x == flag) x = 2;
else x = 3;
}
return;
}
b = tmp;
}
}
occ.back() = -1;
return;
}
} tree;
int occ[nmax];
void dfs(int node) {
if(occ[node] == 1) return;
occ[node] = 1;
for(auto x : leg[node]) {
if(occ[x] == 0) {
tree.addedge(node, x);
dfs(x);
}
}
return;
}
void constr_tree(vector<pii>& edg, int rt) {
tree.clear();
for(int i = 0; i < n; i++)
leg[i].clear();
for(auto [a, b] : edg)
leg[a].emplace_back(b),
leg[b].emplace_back(a);
tree.root = rt;
dfs(rt);
tree.init();
}
int rnd(int x) {return rng() % x;}
vector<int> sol;
void verif(int node, int col) {
sol[node] = -1;
for(auto x : leg[node]) {
if(sol[x] == col) {
verif(x, col);
}
}
}
std::vector<int> find_split(int N, int a, int b, int c, std::vector<int> p, std::vector<int> q) {
n = N;
int hsh[3] = {0, 1, 2};
{ // renumerotare
if(a > b)
swap(hsh[0], hsh[1]),
swap(a, b);
if(b > c)
swap(hsh[1], hsh[2]),
swap(b, c);
if(a > b)
swap(hsh[0], hsh[1]),
swap(a, b);
}
vector<pii> edg;
for(int i = 0; i < sz(p); i++)
edg.emplace_back(p[i], q[i]);
vector<int> var(n, -1);
int counted = 0;
int sus = 0;
do {
constr_tree(edg, sus);
vector<int> var1 = tree.getbydown(a), var2 = tree.getbyroot(a);
tree.fill(var1, b);
tree.fill(var2, b);
if(var1.back() == -1)
swap(var1, var2);
var = move(var1);
counted++;
random_shuffle(all(edg), rnd);
//sus = rnd(n);
} while(var.back() == -1 && counted < 1);
if(var.back() == -1) {
fill(all(var), 0);
return var;
}
sol = var;
int cnts = 0;
for(int i = 0; i < n; i++) {
if(sol[i] == 1)
cnts++,
verif(i, 1);
if(sol[i] == 2)
cnts++,
verif(i, 2);
}
//cerr << cnts << '\n';
assert(cnts == 2);
int cnt[3] = {0, 0, 0};
for(auto &x : var) {
x--;
x = hsh[x];
x++;
}
return var;
}
Compilation message
split.cpp: In function 'void constr_tree(std::vector<std::pair<int, int> >&, int)':
split.cpp:130:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
130 | for(auto [a, b] : edg)
| ^
split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:202:7: warning: unused variable 'cnt' [-Wunused-variable]
202 | int cnt[3] = {0, 0, 0};
| ^~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
4948 KB |
ok, correct split |
2 |
Correct |
3 ms |
4948 KB |
ok, correct split |
3 |
Correct |
3 ms |
4948 KB |
ok, correct split |
4 |
Correct |
3 ms |
5024 KB |
ok, correct split |
5 |
Correct |
3 ms |
4948 KB |
ok, correct split |
6 |
Correct |
3 ms |
5016 KB |
ok, correct split |
7 |
Correct |
112 ms |
25276 KB |
ok, correct split |
8 |
Correct |
103 ms |
23036 KB |
ok, correct split |
9 |
Correct |
103 ms |
22284 KB |
ok, correct split |
10 |
Correct |
92 ms |
25664 KB |
ok, correct split |
11 |
Correct |
105 ms |
25664 KB |
ok, correct split |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
4948 KB |
ok, correct split |
2 |
Correct |
3 ms |
4948 KB |
ok, correct split |
3 |
Correct |
3 ms |
4944 KB |
ok, correct split |
4 |
Correct |
106 ms |
23492 KB |
ok, correct split |
5 |
Correct |
95 ms |
18112 KB |
ok, correct split |
6 |
Correct |
88 ms |
25644 KB |
ok, correct split |
7 |
Correct |
105 ms |
22848 KB |
ok, correct split |
8 |
Correct |
132 ms |
21668 KB |
ok, correct split |
9 |
Correct |
110 ms |
17856 KB |
ok, correct split |
10 |
Correct |
68 ms |
17800 KB |
ok, correct split |
11 |
Correct |
65 ms |
17920 KB |
ok, correct split |
12 |
Correct |
64 ms |
18188 KB |
ok, correct split |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
5016 KB |
ok, correct split |
2 |
Correct |
89 ms |
18052 KB |
ok, correct split |
3 |
Correct |
39 ms |
10252 KB |
ok, correct split |
4 |
Correct |
3 ms |
5012 KB |
ok, correct split |
5 |
Correct |
120 ms |
20628 KB |
ok, correct split |
6 |
Correct |
103 ms |
20624 KB |
ok, correct split |
7 |
Correct |
108 ms |
20072 KB |
ok, correct split |
8 |
Correct |
108 ms |
21304 KB |
ok, correct split |
9 |
Correct |
109 ms |
19848 KB |
ok, correct split |
10 |
Correct |
27 ms |
9372 KB |
ok, no valid answer |
11 |
Correct |
39 ms |
11520 KB |
ok, no valid answer |
12 |
Correct |
83 ms |
18368 KB |
ok, no valid answer |
13 |
Correct |
91 ms |
18056 KB |
ok, no valid answer |
14 |
Correct |
70 ms |
18240 KB |
ok, no valid answer |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
4948 KB |
ok, correct split |
2 |
Correct |
3 ms |
4908 KB |
ok, no valid answer |
3 |
Correct |
3 ms |
4948 KB |
ok, correct split |
4 |
Correct |
3 ms |
4912 KB |
ok, correct split |
5 |
Correct |
3 ms |
4948 KB |
ok, correct split |
6 |
Correct |
3 ms |
5016 KB |
ok, correct split |
7 |
Correct |
2 ms |
4948 KB |
ok, correct split |
8 |
Correct |
3 ms |
4948 KB |
ok, correct split |
9 |
Correct |
5 ms |
5460 KB |
ok, correct split |
10 |
Correct |
5 ms |
5352 KB |
ok, correct split |
11 |
Correct |
3 ms |
4948 KB |
ok, correct split |
12 |
Correct |
6 ms |
5460 KB |
ok, correct split |
13 |
Correct |
3 ms |
5016 KB |
ok, correct split |
14 |
Correct |
3 ms |
4948 KB |
ok, correct split |
15 |
Correct |
3 ms |
5012 KB |
ok, correct split |
16 |
Correct |
3 ms |
4948 KB |
ok, correct split |
17 |
Correct |
2 ms |
4948 KB |
ok, correct split |
18 |
Correct |
3 ms |
4948 KB |
ok, correct split |
19 |
Correct |
3 ms |
5024 KB |
ok, correct split |
20 |
Correct |
3 ms |
5156 KB |
ok, correct split |
21 |
Correct |
4 ms |
5332 KB |
ok, correct split |
22 |
Correct |
4 ms |
5332 KB |
ok, correct split |
23 |
Correct |
4 ms |
5408 KB |
ok, correct split |
24 |
Correct |
5 ms |
5332 KB |
ok, correct split |
25 |
Correct |
5 ms |
5332 KB |
ok, correct split |
26 |
Correct |
5 ms |
5408 KB |
ok, correct split |
27 |
Correct |
4 ms |
5332 KB |
ok, correct split |
28 |
Correct |
6 ms |
5460 KB |
ok, correct split |
29 |
Correct |
3 ms |
4948 KB |
ok, correct split |
30 |
Correct |
5 ms |
5412 KB |
ok, correct split |
31 |
Correct |
3 ms |
5076 KB |
ok, correct split |
32 |
Correct |
3 ms |
4948 KB |
ok, correct split |
33 |
Correct |
4 ms |
5020 KB |
ok, correct split |
34 |
Correct |
4 ms |
5332 KB |
ok, correct split |
35 |
Correct |
4 ms |
5284 KB |
ok, correct split |
36 |
Correct |
4 ms |
5332 KB |
ok, correct split |
37 |
Correct |
5 ms |
5332 KB |
ok, correct split |
38 |
Correct |
5 ms |
5460 KB |
ok, correct split |
39 |
Correct |
5 ms |
5348 KB |
ok, correct split |
40 |
Correct |
5 ms |
5408 KB |
ok, correct split |
41 |
Correct |
4 ms |
5204 KB |
ok, correct split |
42 |
Correct |
4 ms |
5204 KB |
ok, correct split |
43 |
Correct |
5 ms |
5408 KB |
ok, correct split |
44 |
Correct |
4 ms |
5332 KB |
ok, correct split |
45 |
Correct |
5 ms |
5408 KB |
ok, correct split |
46 |
Correct |
4 ms |
5332 KB |
ok, correct split |
47 |
Correct |
4 ms |
5332 KB |
ok, no valid answer |
48 |
Correct |
5 ms |
5332 KB |
ok, correct split |
49 |
Correct |
5 ms |
5332 KB |
ok, correct split |
50 |
Correct |
3 ms |
4972 KB |
ok, no valid answer |
51 |
Correct |
3 ms |
4948 KB |
ok, no valid answer |
52 |
Correct |
5 ms |
5332 KB |
ok, no valid answer |
53 |
Correct |
5 ms |
5332 KB |
ok, no valid answer |
54 |
Correct |
4 ms |
5332 KB |
ok, no valid answer |
55 |
Correct |
5 ms |
5332 KB |
ok, no valid answer |
56 |
Correct |
5 ms |
5332 KB |
ok, no valid answer |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
4948 KB |
ok, correct split |
2 |
Correct |
3 ms |
4948 KB |
ok, correct split |
3 |
Correct |
3 ms |
4948 KB |
ok, correct split |
4 |
Correct |
3 ms |
5024 KB |
ok, correct split |
5 |
Correct |
3 ms |
4948 KB |
ok, correct split |
6 |
Correct |
3 ms |
5016 KB |
ok, correct split |
7 |
Correct |
112 ms |
25276 KB |
ok, correct split |
8 |
Correct |
103 ms |
23036 KB |
ok, correct split |
9 |
Correct |
103 ms |
22284 KB |
ok, correct split |
10 |
Correct |
92 ms |
25664 KB |
ok, correct split |
11 |
Correct |
105 ms |
25664 KB |
ok, correct split |
12 |
Correct |
3 ms |
4948 KB |
ok, correct split |
13 |
Correct |
3 ms |
4948 KB |
ok, correct split |
14 |
Correct |
3 ms |
4944 KB |
ok, correct split |
15 |
Correct |
106 ms |
23492 KB |
ok, correct split |
16 |
Correct |
95 ms |
18112 KB |
ok, correct split |
17 |
Correct |
88 ms |
25644 KB |
ok, correct split |
18 |
Correct |
105 ms |
22848 KB |
ok, correct split |
19 |
Correct |
132 ms |
21668 KB |
ok, correct split |
20 |
Correct |
110 ms |
17856 KB |
ok, correct split |
21 |
Correct |
68 ms |
17800 KB |
ok, correct split |
22 |
Correct |
65 ms |
17920 KB |
ok, correct split |
23 |
Correct |
64 ms |
18188 KB |
ok, correct split |
24 |
Correct |
4 ms |
5016 KB |
ok, correct split |
25 |
Correct |
89 ms |
18052 KB |
ok, correct split |
26 |
Correct |
39 ms |
10252 KB |
ok, correct split |
27 |
Correct |
3 ms |
5012 KB |
ok, correct split |
28 |
Correct |
120 ms |
20628 KB |
ok, correct split |
29 |
Correct |
103 ms |
20624 KB |
ok, correct split |
30 |
Correct |
108 ms |
20072 KB |
ok, correct split |
31 |
Correct |
108 ms |
21304 KB |
ok, correct split |
32 |
Correct |
109 ms |
19848 KB |
ok, correct split |
33 |
Correct |
27 ms |
9372 KB |
ok, no valid answer |
34 |
Correct |
39 ms |
11520 KB |
ok, no valid answer |
35 |
Correct |
83 ms |
18368 KB |
ok, no valid answer |
36 |
Correct |
91 ms |
18056 KB |
ok, no valid answer |
37 |
Correct |
70 ms |
18240 KB |
ok, no valid answer |
38 |
Correct |
3 ms |
4948 KB |
ok, correct split |
39 |
Correct |
3 ms |
4908 KB |
ok, no valid answer |
40 |
Correct |
3 ms |
4948 KB |
ok, correct split |
41 |
Correct |
3 ms |
4912 KB |
ok, correct split |
42 |
Correct |
3 ms |
4948 KB |
ok, correct split |
43 |
Correct |
3 ms |
5016 KB |
ok, correct split |
44 |
Correct |
2 ms |
4948 KB |
ok, correct split |
45 |
Correct |
3 ms |
4948 KB |
ok, correct split |
46 |
Correct |
5 ms |
5460 KB |
ok, correct split |
47 |
Correct |
5 ms |
5352 KB |
ok, correct split |
48 |
Correct |
3 ms |
4948 KB |
ok, correct split |
49 |
Correct |
6 ms |
5460 KB |
ok, correct split |
50 |
Correct |
3 ms |
5016 KB |
ok, correct split |
51 |
Correct |
3 ms |
4948 KB |
ok, correct split |
52 |
Correct |
3 ms |
5012 KB |
ok, correct split |
53 |
Correct |
3 ms |
4948 KB |
ok, correct split |
54 |
Correct |
2 ms |
4948 KB |
ok, correct split |
55 |
Correct |
3 ms |
4948 KB |
ok, correct split |
56 |
Correct |
3 ms |
5024 KB |
ok, correct split |
57 |
Correct |
3 ms |
5156 KB |
ok, correct split |
58 |
Correct |
4 ms |
5332 KB |
ok, correct split |
59 |
Correct |
4 ms |
5332 KB |
ok, correct split |
60 |
Correct |
4 ms |
5408 KB |
ok, correct split |
61 |
Correct |
5 ms |
5332 KB |
ok, correct split |
62 |
Correct |
5 ms |
5332 KB |
ok, correct split |
63 |
Correct |
5 ms |
5408 KB |
ok, correct split |
64 |
Correct |
4 ms |
5332 KB |
ok, correct split |
65 |
Correct |
6 ms |
5460 KB |
ok, correct split |
66 |
Correct |
3 ms |
4948 KB |
ok, correct split |
67 |
Correct |
5 ms |
5412 KB |
ok, correct split |
68 |
Correct |
3 ms |
5076 KB |
ok, correct split |
69 |
Correct |
3 ms |
4948 KB |
ok, correct split |
70 |
Correct |
4 ms |
5020 KB |
ok, correct split |
71 |
Correct |
4 ms |
5332 KB |
ok, correct split |
72 |
Correct |
4 ms |
5284 KB |
ok, correct split |
73 |
Correct |
4 ms |
5332 KB |
ok, correct split |
74 |
Correct |
5 ms |
5332 KB |
ok, correct split |
75 |
Correct |
5 ms |
5460 KB |
ok, correct split |
76 |
Correct |
5 ms |
5348 KB |
ok, correct split |
77 |
Correct |
5 ms |
5408 KB |
ok, correct split |
78 |
Correct |
4 ms |
5204 KB |
ok, correct split |
79 |
Correct |
4 ms |
5204 KB |
ok, correct split |
80 |
Correct |
5 ms |
5408 KB |
ok, correct split |
81 |
Correct |
4 ms |
5332 KB |
ok, correct split |
82 |
Correct |
5 ms |
5408 KB |
ok, correct split |
83 |
Correct |
4 ms |
5332 KB |
ok, correct split |
84 |
Correct |
4 ms |
5332 KB |
ok, no valid answer |
85 |
Correct |
5 ms |
5332 KB |
ok, correct split |
86 |
Correct |
5 ms |
5332 KB |
ok, correct split |
87 |
Correct |
3 ms |
4972 KB |
ok, no valid answer |
88 |
Correct |
3 ms |
4948 KB |
ok, no valid answer |
89 |
Correct |
5 ms |
5332 KB |
ok, no valid answer |
90 |
Correct |
5 ms |
5332 KB |
ok, no valid answer |
91 |
Correct |
4 ms |
5332 KB |
ok, no valid answer |
92 |
Correct |
5 ms |
5332 KB |
ok, no valid answer |
93 |
Correct |
5 ms |
5332 KB |
ok, no valid answer |
94 |
Correct |
104 ms |
21048 KB |
ok, correct split |
95 |
Correct |
144 ms |
26648 KB |
ok, correct split |
96 |
Correct |
140 ms |
24832 KB |
ok, correct split |
97 |
Correct |
30 ms |
10180 KB |
ok, correct split |
98 |
Correct |
30 ms |
10384 KB |
ok, correct split |
99 |
Correct |
48 ms |
12812 KB |
ok, correct split |
100 |
Correct |
128 ms |
22340 KB |
ok, correct split |
101 |
Correct |
122 ms |
21032 KB |
ok, correct split |
102 |
Correct |
117 ms |
20796 KB |
ok, correct split |
103 |
Correct |
109 ms |
20488 KB |
ok, correct split |
104 |
Correct |
109 ms |
22596 KB |
ok, correct split |
105 |
Correct |
53 ms |
13080 KB |
ok, correct split |
106 |
Correct |
110 ms |
22024 KB |
ok, correct split |
107 |
Correct |
93 ms |
18064 KB |
ok, correct split |
108 |
Correct |
93 ms |
18100 KB |
ok, correct split |
109 |
Correct |
164 ms |
21684 KB |
ok, correct split |
110 |
Correct |
138 ms |
21788 KB |
ok, correct split |
111 |
Correct |
140 ms |
21840 KB |
ok, correct split |
112 |
Correct |
137 ms |
22052 KB |
ok, correct split |
113 |
Correct |
129 ms |
22048 KB |
ok, correct split |
114 |
Correct |
13 ms |
6992 KB |
ok, correct split |
115 |
Correct |
12 ms |
6736 KB |
ok, correct split |
116 |
Correct |
120 ms |
21772 KB |
ok, correct split |
117 |
Correct |
134 ms |
21760 KB |
ok, correct split |
118 |
Correct |
95 ms |
18052 KB |
ok, correct split |
119 |
Correct |
97 ms |
17984 KB |
ok, correct split |
120 |
Correct |
103 ms |
21952 KB |
ok, correct split |
121 |
Correct |
117 ms |
18072 KB |
ok, no valid answer |
122 |
Correct |
88 ms |
18204 KB |
ok, no valid answer |
123 |
Correct |
148 ms |
22544 KB |
ok, no valid answer |
124 |
Correct |
138 ms |
22480 KB |
ok, no valid answer |
125 |
Correct |
94 ms |
19664 KB |
ok, no valid answer |
126 |
Correct |
68 ms |
16996 KB |
ok, no valid answer |
127 |
Correct |
104 ms |
20232 KB |
ok, no valid answer |