#include "split.h"
//#include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
#define all(s) s.begin(), s.end()
#define ok puts("ok")
#define ll long long
#define pb push_back
#define mk make_pair
#define fr first
#define sc second
#define vi vector < int >
#define pi pair < int, int >
const int MAXN = 2e5 + 7;
const int INF = 1e9 + 7;
int tin[MAXN], tim;
int clr[MAXN];
int h[MAXN], sz[MAXN], mn[MAXN];
int x, y, z;
vi g[MAXN], palette;
bool invalid = false;
void precalc (int v, int p = 0){
tin[v] = ++tim;
clr[v] = palette[1];
h[v] = h[p] + 1;
sz[v] = 1;
mn[v] = h[v];
for (int to : g[v]){
if (!h[to]){
precalc(to, v);
sz[v] += sz[to];
mn[v] = min(mn[v], mn[to]);
}
else
mn[v] = min(mn[v], h[to]);
}
}
void paint_main (int v, int cclr = 0){
if (cclr == 0 && clr[v] == palette[1]){
x--; y++;
}
else if (cclr == 1 && clr[v] == palette[0]){
x++; y--;
}
clr[v] = palette[cclr];
for (int to : g[v])
if (h[to] - h[v] == 1)
paint_main(to, cclr);
}
void paint (int v, int point){
if (y <= 0)
return;
if (mn[v] < point)
paint_main(v, 1);
else {
for (int to : g[v])
if (h[to] - h[v] == 1 && y > 0)
paint(to, point);
}
}
void dfs (int v){
pi mx = {0, 0};
for (int to : g[v])
if (h[to] - h[v] == 1 && mx.fr < sz[to])
mx = {sz[to], to};
if (x < mx.fr)
dfs(mx.sc);
else {
paint_main(v);
for (int to : g[v])
if (h[to] - h[v] == 1 && y > 0)
paint(to, h[v]);
if (y > 0)
invalid = true;
}
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
if (a >= b && a >= c){
if (b >= c){
palette = {2, 3, 1};
swap(b, c);
}
else
palette = {3, 2, 1};
swap(a, c);
}
else if (b >= a && b >= c){
if (a >= c)
palette = {1, 3, 2};
else {
palette = {3, 1, 2};
swap(a, c);
}
swap(b, c);
}
else {
if (b >= a){
palette = {2, 1, 3};
swap(a, b);
}
else
palette = {1, 2, 3};
}
x = a;
y = b;
z = c;
for (int i = 0; i < p.size(); i++){
g[p[i] + 1].pb(q[i] + 1);
g[q[i] + 1].pb(p[i] + 1);
}
vector < int > res;
precalc(1);
y -= n;
bool stop = false;
for (int i = 2; i <= n; i++){
if (sz[i] >= a && sz[1] - sz[i] >= b){
paint_main(i);
stop = true;
break;
}
if (sz[i] >= b && sz[1] - sz[i] >= a){
paint_main(1);
paint_main(i, 1);
stop = true;
break;
}
}
if (stop == false)
dfs(1);
if (invalid == true)
while (res.size() < n)
res.pb(0);
else {
vector < pi > temp;
for (int i = 1; i <= n; i++)
temp.pb({tin[i], i});
sort(all(temp));
for (int i = n - 1; i >= 0; i--){
if (clr[temp[i].sc] == palette[0] && x < 0){
clr[temp[i].sc] = palette[2];
x++;
}
else if (clr[temp[i].sc] == palette[1] && y < 0){
clr[temp[i].sc] = palette[2];
y++;
}
}
for (int i = 1; i <= n; i++)
res.pb(clr[i]);
}
return res;
}
Compilation message
split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:118:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < p.size(); i++){
~~^~~~~~~~~~
split.cpp:143:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while (res.size() < n)
~~~~~~~~~~~^~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
4992 KB |
ok, correct split |
2 |
Correct |
3 ms |
4992 KB |
ok, correct split |
3 |
Correct |
3 ms |
4992 KB |
ok, correct split |
4 |
Correct |
4 ms |
4992 KB |
ok, correct split |
5 |
Correct |
4 ms |
4992 KB |
ok, correct split |
6 |
Correct |
4 ms |
4992 KB |
ok, correct split |
7 |
Correct |
115 ms |
19056 KB |
ok, correct split |
8 |
Correct |
103 ms |
17648 KB |
ok, correct split |
9 |
Correct |
132 ms |
17264 KB |
ok, correct split |
10 |
Correct |
114 ms |
18928 KB |
ok, correct split |
11 |
Correct |
115 ms |
19088 KB |
ok, correct split |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
4992 KB |
ok, correct split |
2 |
Correct |
4 ms |
4992 KB |
ok, correct split |
3 |
Correct |
4 ms |
4992 KB |
ok, correct split |
4 |
Correct |
134 ms |
16620 KB |
ok, correct split |
5 |
Correct |
100 ms |
14576 KB |
ok, correct split |
6 |
Correct |
107 ms |
19184 KB |
ok, correct split |
7 |
Correct |
121 ms |
17520 KB |
ok, correct split |
8 |
Correct |
165 ms |
17008 KB |
ok, correct split |
9 |
Correct |
118 ms |
14576 KB |
ok, correct split |
10 |
Correct |
77 ms |
14572 KB |
ok, correct split |
11 |
Correct |
77 ms |
14572 KB |
ok, correct split |
12 |
Correct |
85 ms |
14956 KB |
ok, correct split |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
4992 KB |
ok, correct split |
2 |
Correct |
109 ms |
13552 KB |
ok, correct split |
3 |
Correct |
37 ms |
8948 KB |
ok, correct split |
4 |
Correct |
4 ms |
4992 KB |
ok, correct split |
5 |
Correct |
116 ms |
16112 KB |
ok, correct split |
6 |
Correct |
133 ms |
15984 KB |
ok, correct split |
7 |
Correct |
125 ms |
15856 KB |
ok, correct split |
8 |
Correct |
133 ms |
16624 KB |
ok, correct split |
9 |
Correct |
111 ms |
15836 KB |
ok, correct split |
10 |
Correct |
28 ms |
8056 KB |
ok, no valid answer |
11 |
Correct |
40 ms |
9336 KB |
ok, no valid answer |
12 |
Correct |
80 ms |
13940 KB |
ok, no valid answer |
13 |
Correct |
101 ms |
13664 KB |
ok, no valid answer |
14 |
Correct |
71 ms |
14064 KB |
ok, no valid answer |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
4992 KB |
ok, correct split |
2 |
Correct |
3 ms |
4992 KB |
ok, no valid answer |
3 |
Correct |
3 ms |
4992 KB |
ok, correct split |
4 |
Correct |
3 ms |
4992 KB |
ok, correct split |
5 |
Correct |
4 ms |
4992 KB |
ok, correct split |
6 |
Correct |
4 ms |
4992 KB |
ok, correct split |
7 |
Correct |
4 ms |
4992 KB |
ok, correct split |
8 |
Correct |
4 ms |
4992 KB |
ok, correct split |
9 |
Correct |
7 ms |
5376 KB |
ok, correct split |
10 |
Correct |
6 ms |
5504 KB |
ok, correct split |
11 |
Correct |
4 ms |
5120 KB |
ok, correct split |
12 |
Correct |
7 ms |
5376 KB |
ok, correct split |
13 |
Correct |
4 ms |
4992 KB |
ok, correct split |
14 |
Correct |
4 ms |
4992 KB |
ok, correct split |
15 |
Correct |
4 ms |
4992 KB |
ok, correct split |
16 |
Correct |
4 ms |
4992 KB |
ok, correct split |
17 |
Correct |
4 ms |
4992 KB |
ok, correct split |
18 |
Correct |
4 ms |
4992 KB |
ok, correct split |
19 |
Correct |
4 ms |
5120 KB |
ok, correct split |
20 |
Correct |
4 ms |
5120 KB |
ok, correct split |
21 |
Correct |
6 ms |
5376 KB |
ok, correct split |
22 |
Correct |
6 ms |
5376 KB |
ok, correct split |
23 |
Correct |
6 ms |
5376 KB |
ok, correct split |
24 |
Correct |
6 ms |
5376 KB |
ok, correct split |
25 |
Correct |
5 ms |
5376 KB |
ok, correct split |
26 |
Correct |
6 ms |
5376 KB |
ok, correct split |
27 |
Correct |
6 ms |
5376 KB |
ok, correct split |
28 |
Correct |
6 ms |
5376 KB |
ok, correct split |
29 |
Correct |
4 ms |
5120 KB |
ok, correct split |
30 |
Correct |
7 ms |
5376 KB |
ok, correct split |
31 |
Correct |
5 ms |
5120 KB |
ok, correct split |
32 |
Correct |
4 ms |
5120 KB |
ok, correct split |
33 |
Correct |
4 ms |
5120 KB |
ok, correct split |
34 |
Correct |
6 ms |
5376 KB |
ok, correct split |
35 |
Correct |
6 ms |
5376 KB |
ok, correct split |
36 |
Correct |
5 ms |
5248 KB |
ok, correct split |
37 |
Correct |
6 ms |
5376 KB |
ok, correct split |
38 |
Correct |
6 ms |
5376 KB |
ok, correct split |
39 |
Correct |
6 ms |
5376 KB |
ok, correct split |
40 |
Correct |
6 ms |
5376 KB |
ok, correct split |
41 |
Correct |
5 ms |
5120 KB |
ok, correct split |
42 |
Correct |
5 ms |
5248 KB |
ok, correct split |
43 |
Correct |
6 ms |
5376 KB |
ok, correct split |
44 |
Correct |
6 ms |
5376 KB |
ok, correct split |
45 |
Correct |
6 ms |
5376 KB |
ok, correct split |
46 |
Correct |
5 ms |
5376 KB |
ok, correct split |
47 |
Correct |
6 ms |
5248 KB |
ok, no valid answer |
48 |
Correct |
5 ms |
5248 KB |
ok, correct split |
49 |
Correct |
5 ms |
5376 KB |
ok, correct split |
50 |
Correct |
3 ms |
4992 KB |
ok, no valid answer |
51 |
Correct |
3 ms |
4992 KB |
ok, no valid answer |
52 |
Correct |
5 ms |
5248 KB |
ok, no valid answer |
53 |
Correct |
6 ms |
5376 KB |
ok, no valid answer |
54 |
Correct |
5 ms |
5248 KB |
ok, no valid answer |
55 |
Correct |
7 ms |
5376 KB |
ok, no valid answer |
56 |
Correct |
5 ms |
5248 KB |
ok, no valid answer |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
4992 KB |
ok, correct split |
2 |
Correct |
3 ms |
4992 KB |
ok, correct split |
3 |
Correct |
3 ms |
4992 KB |
ok, correct split |
4 |
Correct |
4 ms |
4992 KB |
ok, correct split |
5 |
Correct |
4 ms |
4992 KB |
ok, correct split |
6 |
Correct |
4 ms |
4992 KB |
ok, correct split |
7 |
Correct |
115 ms |
19056 KB |
ok, correct split |
8 |
Correct |
103 ms |
17648 KB |
ok, correct split |
9 |
Correct |
132 ms |
17264 KB |
ok, correct split |
10 |
Correct |
114 ms |
18928 KB |
ok, correct split |
11 |
Correct |
115 ms |
19088 KB |
ok, correct split |
12 |
Correct |
3 ms |
4992 KB |
ok, correct split |
13 |
Correct |
4 ms |
4992 KB |
ok, correct split |
14 |
Correct |
4 ms |
4992 KB |
ok, correct split |
15 |
Correct |
134 ms |
16620 KB |
ok, correct split |
16 |
Correct |
100 ms |
14576 KB |
ok, correct split |
17 |
Correct |
107 ms |
19184 KB |
ok, correct split |
18 |
Correct |
121 ms |
17520 KB |
ok, correct split |
19 |
Correct |
165 ms |
17008 KB |
ok, correct split |
20 |
Correct |
118 ms |
14576 KB |
ok, correct split |
21 |
Correct |
77 ms |
14572 KB |
ok, correct split |
22 |
Correct |
77 ms |
14572 KB |
ok, correct split |
23 |
Correct |
85 ms |
14956 KB |
ok, correct split |
24 |
Correct |
3 ms |
4992 KB |
ok, correct split |
25 |
Correct |
109 ms |
13552 KB |
ok, correct split |
26 |
Correct |
37 ms |
8948 KB |
ok, correct split |
27 |
Correct |
4 ms |
4992 KB |
ok, correct split |
28 |
Correct |
116 ms |
16112 KB |
ok, correct split |
29 |
Correct |
133 ms |
15984 KB |
ok, correct split |
30 |
Correct |
125 ms |
15856 KB |
ok, correct split |
31 |
Correct |
133 ms |
16624 KB |
ok, correct split |
32 |
Correct |
111 ms |
15836 KB |
ok, correct split |
33 |
Correct |
28 ms |
8056 KB |
ok, no valid answer |
34 |
Correct |
40 ms |
9336 KB |
ok, no valid answer |
35 |
Correct |
80 ms |
13940 KB |
ok, no valid answer |
36 |
Correct |
101 ms |
13664 KB |
ok, no valid answer |
37 |
Correct |
71 ms |
14064 KB |
ok, no valid answer |
38 |
Correct |
3 ms |
4992 KB |
ok, correct split |
39 |
Correct |
3 ms |
4992 KB |
ok, no valid answer |
40 |
Correct |
3 ms |
4992 KB |
ok, correct split |
41 |
Correct |
3 ms |
4992 KB |
ok, correct split |
42 |
Correct |
4 ms |
4992 KB |
ok, correct split |
43 |
Correct |
4 ms |
4992 KB |
ok, correct split |
44 |
Correct |
4 ms |
4992 KB |
ok, correct split |
45 |
Correct |
4 ms |
4992 KB |
ok, correct split |
46 |
Correct |
7 ms |
5376 KB |
ok, correct split |
47 |
Correct |
6 ms |
5504 KB |
ok, correct split |
48 |
Correct |
4 ms |
5120 KB |
ok, correct split |
49 |
Correct |
7 ms |
5376 KB |
ok, correct split |
50 |
Correct |
4 ms |
4992 KB |
ok, correct split |
51 |
Correct |
4 ms |
4992 KB |
ok, correct split |
52 |
Correct |
4 ms |
4992 KB |
ok, correct split |
53 |
Correct |
4 ms |
4992 KB |
ok, correct split |
54 |
Correct |
4 ms |
4992 KB |
ok, correct split |
55 |
Correct |
4 ms |
4992 KB |
ok, correct split |
56 |
Correct |
4 ms |
5120 KB |
ok, correct split |
57 |
Correct |
4 ms |
5120 KB |
ok, correct split |
58 |
Correct |
6 ms |
5376 KB |
ok, correct split |
59 |
Correct |
6 ms |
5376 KB |
ok, correct split |
60 |
Correct |
6 ms |
5376 KB |
ok, correct split |
61 |
Correct |
6 ms |
5376 KB |
ok, correct split |
62 |
Correct |
5 ms |
5376 KB |
ok, correct split |
63 |
Correct |
6 ms |
5376 KB |
ok, correct split |
64 |
Correct |
6 ms |
5376 KB |
ok, correct split |
65 |
Correct |
6 ms |
5376 KB |
ok, correct split |
66 |
Correct |
4 ms |
5120 KB |
ok, correct split |
67 |
Correct |
7 ms |
5376 KB |
ok, correct split |
68 |
Correct |
5 ms |
5120 KB |
ok, correct split |
69 |
Correct |
4 ms |
5120 KB |
ok, correct split |
70 |
Correct |
4 ms |
5120 KB |
ok, correct split |
71 |
Correct |
6 ms |
5376 KB |
ok, correct split |
72 |
Correct |
6 ms |
5376 KB |
ok, correct split |
73 |
Correct |
5 ms |
5248 KB |
ok, correct split |
74 |
Correct |
6 ms |
5376 KB |
ok, correct split |
75 |
Correct |
6 ms |
5376 KB |
ok, correct split |
76 |
Correct |
6 ms |
5376 KB |
ok, correct split |
77 |
Correct |
6 ms |
5376 KB |
ok, correct split |
78 |
Correct |
5 ms |
5120 KB |
ok, correct split |
79 |
Correct |
5 ms |
5248 KB |
ok, correct split |
80 |
Correct |
6 ms |
5376 KB |
ok, correct split |
81 |
Correct |
6 ms |
5376 KB |
ok, correct split |
82 |
Correct |
6 ms |
5376 KB |
ok, correct split |
83 |
Correct |
5 ms |
5376 KB |
ok, correct split |
84 |
Correct |
6 ms |
5248 KB |
ok, no valid answer |
85 |
Correct |
5 ms |
5248 KB |
ok, correct split |
86 |
Correct |
5 ms |
5376 KB |
ok, correct split |
87 |
Correct |
3 ms |
4992 KB |
ok, no valid answer |
88 |
Correct |
3 ms |
4992 KB |
ok, no valid answer |
89 |
Correct |
5 ms |
5248 KB |
ok, no valid answer |
90 |
Correct |
6 ms |
5376 KB |
ok, no valid answer |
91 |
Correct |
5 ms |
5248 KB |
ok, no valid answer |
92 |
Correct |
7 ms |
5376 KB |
ok, no valid answer |
93 |
Correct |
5 ms |
5248 KB |
ok, no valid answer |
94 |
Correct |
127 ms |
16628 KB |
ok, correct split |
95 |
Correct |
181 ms |
21104 KB |
ok, correct split |
96 |
Correct |
153 ms |
19564 KB |
ok, correct split |
97 |
Correct |
37 ms |
8948 KB |
ok, correct split |
98 |
Correct |
37 ms |
9076 KB |
ok, correct split |
99 |
Correct |
61 ms |
11104 KB |
ok, correct split |
100 |
Correct |
154 ms |
18540 KB |
ok, correct split |
101 |
Correct |
144 ms |
17260 KB |
ok, correct split |
102 |
Correct |
131 ms |
16876 KB |
ok, correct split |
103 |
Correct |
120 ms |
16620 KB |
ok, correct split |
104 |
Correct |
136 ms |
18140 KB |
ok, correct split |
105 |
Correct |
58 ms |
10992 KB |
ok, correct split |
106 |
Correct |
135 ms |
18148 KB |
ok, correct split |
107 |
Correct |
120 ms |
14708 KB |
ok, correct split |
108 |
Correct |
113 ms |
14704 KB |
ok, correct split |
109 |
Correct |
170 ms |
17904 KB |
ok, correct split |
110 |
Correct |
178 ms |
17900 KB |
ok, correct split |
111 |
Correct |
176 ms |
17772 KB |
ok, correct split |
112 |
Correct |
158 ms |
18028 KB |
ok, correct split |
113 |
Correct |
176 ms |
18028 KB |
ok, correct split |
114 |
Correct |
18 ms |
6656 KB |
ok, correct split |
115 |
Correct |
15 ms |
6448 KB |
ok, correct split |
116 |
Correct |
161 ms |
17768 KB |
ok, correct split |
117 |
Correct |
154 ms |
17584 KB |
ok, correct split |
118 |
Correct |
99 ms |
14576 KB |
ok, correct split |
119 |
Correct |
104 ms |
14576 KB |
ok, correct split |
120 |
Correct |
111 ms |
17008 KB |
ok, correct split |
121 |
Correct |
97 ms |
13556 KB |
ok, no valid answer |
122 |
Correct |
104 ms |
13684 KB |
ok, no valid answer |
123 |
Correct |
160 ms |
17656 KB |
ok, no valid answer |
124 |
Correct |
162 ms |
17532 KB |
ok, no valid answer |
125 |
Correct |
101 ms |
14832 KB |
ok, no valid answer |
126 |
Correct |
60 ms |
13136 KB |
ok, no valid answer |
127 |
Correct |
122 ms |
15348 KB |
ok, no valid answer |