#include "split.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
const int len = 1e5+5;
vector<int> adj[len];
int vis[len], num[len], low[len], par[len], sz[len];
int n, sz1, sz2, sz3, col1, col2, col3, cnt;
void fix(int u){
num[u] = low[u] = ++cnt;
sz[u] = 1;
for (auto v: adj[u]){
if (!num[v]){
par[v] = u;
fix(v);
sz[u] += sz[v];
low[u] = min(low[u], low[v]);
}
else if (v != par[u] && num[v] < num[u])
low[u] = min(low[u], num[v]);
}
}
void add(int u, vector<int> &mys){
mys.pb(u);
for (auto v: adj[u]){
if (par[v] != u) continue;
add(v, mys);
}
}
void dfs(int u, vector<int> &mys){
for (auto v: adj[u]){
if (par[v] != u) continue;
if (sz[v] >= sz1)
return void(dfs(v, mys));
}
mys.pb(u);
vector<int> temp;
for (auto v: adj[u]){
if (par[v] != u) continue;
if (low[v] >= num[u])
add(v, mys);
else
temp.pb(v);
}
while (mys.size() < sz1){
add(temp.back(), mys);
temp.pop_back();
}
return;
}
void paint(int u, int &rem, int col){
//printf("painting: u = %d, rem = %d, col = %d\n", u, rem, col);
vis[u] = col, rem--;
if (rem == 0) return;
for (auto v: adj[u]){
if (vis[v]) continue;
paint(v, rem, col);
if (rem == 0) return;
}
}
void print(vector<int> vec){
for (auto cur: vec)
printf("%d ", cur);
printf("\n");
}
vector<int> find_split(int N, int A, int B, int C, vector<int> P, vector<int> Q) {
n = N;
sz1 = A, sz2 = B, sz3 = C;
col1 = 1, col2 = 2, col3 = 3;
if (sz2 < sz1)
swap(sz2, sz1), swap(col2, col1);
if (sz3 < sz1)
swap(sz3, sz1), swap(col3, col1);
if (sz3 < sz2)
swap(sz3, sz2), swap(col3, col2);
for (int i = 0; i < P.size(); i++){
int a = P[i], b = Q[i];
a++, b++;
adj[a].pb(b);
adj[b].pb(a);
}
fix(1);
vector<int> fir, sec;
dfs(1, fir);
sort(fir.begin(), fir.end());
for (int i = 1, j = 0; i <= n; i++){
while (j < fir.size() && fir[j] < i)
j++;
if (j < fir.size() && fir[j] == i)
continue;
sec.pb(i);
}
if (fir.size() >= sec.size())
swap(fir, sec);
//printf("fir: "), print(fir);
//printf("sec: "), print(sec);
if (fir.size() >= sz1){
for (auto u: sec)
vis[u] = col3;
paint(fir.back(), sz1, col1);
for (int u: fir)
if (!vis[u])
vis[u] = col3;
for (int u: sec)
vis[u] = 0;
paint(sec.back(), sz2, col2);
for (int u: sec)
if (!vis[u])
vis[u] = col3;
}
vector<int> out(n, 0);
for (int i = 1; i <= n; i++)
out[i-1] = vis[i];
return out;
}
Compilation message
split.cpp: In function 'void dfs(int, std::vector<int>&)':
split.cpp:57:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
57 | while (mys.size() < sz1){
| ~~~~~~~~~~~^~~~~
split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:92:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
92 | if (sz3 < sz2)
| ^~
split.cpp:95:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
95 | for (int i = 0; i < P.size(); i++){
| ^~~
split.cpp:95:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
95 | for (int i = 0; i < P.size(); i++){
| ~~^~~~~~~~~~
split.cpp:109:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
109 | while (j < fir.size() && fir[j] < i)
| ~~^~~~~~~~~~~~
split.cpp:112:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
112 | if (j < fir.size() && fir[j] == i)
| ~~^~~~~~~~~~~~
split.cpp:123:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
123 | if (fir.size() >= sz1){
| ~~~~~~~~~~~^~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2688 KB |
ok, correct split |
2 |
Correct |
2 ms |
2688 KB |
ok, correct split |
3 |
Correct |
2 ms |
2688 KB |
ok, correct split |
4 |
Correct |
2 ms |
2688 KB |
ok, correct split |
5 |
Correct |
2 ms |
2688 KB |
ok, correct split |
6 |
Correct |
3 ms |
2688 KB |
ok, correct split |
7 |
Correct |
125 ms |
18800 KB |
ok, correct split |
8 |
Correct |
101 ms |
14556 KB |
ok, correct split |
9 |
Correct |
121 ms |
15644 KB |
ok, correct split |
10 |
Correct |
114 ms |
20724 KB |
ok, correct split |
11 |
Correct |
122 ms |
19184 KB |
ok, correct split |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2688 KB |
ok, correct split |
2 |
Correct |
2 ms |
2688 KB |
ok, correct split |
3 |
Correct |
2 ms |
2688 KB |
ok, correct split |
4 |
Correct |
123 ms |
14832 KB |
ok, correct split |
5 |
Correct |
96 ms |
11508 KB |
ok, correct split |
6 |
Correct |
121 ms |
20724 KB |
ok, correct split |
7 |
Correct |
116 ms |
17396 KB |
ok, correct split |
8 |
Correct |
143 ms |
13812 KB |
ok, correct split |
9 |
Correct |
100 ms |
11508 KB |
ok, correct split |
10 |
Correct |
62 ms |
11504 KB |
ok, correct split |
11 |
Correct |
65 ms |
11376 KB |
ok, correct split |
12 |
Correct |
68 ms |
11888 KB |
ok, correct split |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2688 KB |
ok, correct split |
2 |
Correct |
108 ms |
10340 KB |
ok, correct split |
3 |
Correct |
30 ms |
5884 KB |
ok, correct split |
4 |
Correct |
2 ms |
2688 KB |
ok, correct split |
5 |
Correct |
116 ms |
12144 KB |
ok, correct split |
6 |
Correct |
111 ms |
11632 KB |
ok, correct split |
7 |
Correct |
121 ms |
12020 KB |
ok, correct split |
8 |
Correct |
116 ms |
13040 KB |
ok, correct split |
9 |
Correct |
124 ms |
11764 KB |
ok, correct split |
10 |
Correct |
28 ms |
5248 KB |
ok, no valid answer |
11 |
Correct |
42 ms |
6516 KB |
ok, no valid answer |
12 |
Correct |
88 ms |
10224 KB |
ok, no valid answer |
13 |
Correct |
99 ms |
9904 KB |
ok, no valid answer |
14 |
Correct |
70 ms |
10224 KB |
ok, no valid answer |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2688 KB |
ok, correct split |
2 |
Correct |
2 ms |
2688 KB |
ok, no valid answer |
3 |
Correct |
2 ms |
2688 KB |
ok, correct split |
4 |
Correct |
2 ms |
2688 KB |
ok, correct split |
5 |
Correct |
2 ms |
2688 KB |
ok, correct split |
6 |
Correct |
2 ms |
2688 KB |
ok, correct split |
7 |
Correct |
2 ms |
2688 KB |
ok, correct split |
8 |
Correct |
2 ms |
2688 KB |
ok, correct split |
9 |
Correct |
5 ms |
3072 KB |
ok, correct split |
10 |
Correct |
5 ms |
2944 KB |
ok, correct split |
11 |
Correct |
2 ms |
2688 KB |
ok, correct split |
12 |
Correct |
5 ms |
2944 KB |
ok, correct split |
13 |
Correct |
2 ms |
2688 KB |
ok, correct split |
14 |
Correct |
2 ms |
2688 KB |
ok, correct split |
15 |
Correct |
2 ms |
2688 KB |
ok, correct split |
16 |
Correct |
2 ms |
2688 KB |
ok, correct split |
17 |
Correct |
2 ms |
2688 KB |
ok, correct split |
18 |
Correct |
2 ms |
2816 KB |
ok, correct split |
19 |
Correct |
2 ms |
2688 KB |
ok, correct split |
20 |
Correct |
3 ms |
2816 KB |
ok, correct split |
21 |
Correct |
5 ms |
2944 KB |
ok, correct split |
22 |
Correct |
4 ms |
2944 KB |
ok, correct split |
23 |
Correct |
4 ms |
2944 KB |
ok, correct split |
24 |
Correct |
4 ms |
2944 KB |
ok, correct split |
25 |
Correct |
4 ms |
2944 KB |
ok, correct split |
26 |
Correct |
4 ms |
2944 KB |
ok, correct split |
27 |
Correct |
4 ms |
2944 KB |
ok, correct split |
28 |
Correct |
4 ms |
2944 KB |
ok, correct split |
29 |
Correct |
2 ms |
2688 KB |
ok, correct split |
30 |
Correct |
4 ms |
2944 KB |
ok, correct split |
31 |
Correct |
3 ms |
2816 KB |
ok, correct split |
32 |
Correct |
2 ms |
2688 KB |
ok, correct split |
33 |
Correct |
2 ms |
2688 KB |
ok, correct split |
34 |
Correct |
4 ms |
2944 KB |
ok, correct split |
35 |
Correct |
5 ms |
2944 KB |
ok, correct split |
36 |
Correct |
4 ms |
2944 KB |
ok, correct split |
37 |
Correct |
5 ms |
2944 KB |
ok, correct split |
38 |
Correct |
6 ms |
2944 KB |
ok, correct split |
39 |
Correct |
5 ms |
2944 KB |
ok, correct split |
40 |
Correct |
4 ms |
2944 KB |
ok, correct split |
41 |
Correct |
3 ms |
2816 KB |
ok, correct split |
42 |
Correct |
3 ms |
2816 KB |
ok, correct split |
43 |
Correct |
5 ms |
2944 KB |
ok, correct split |
44 |
Correct |
4 ms |
2944 KB |
ok, correct split |
45 |
Correct |
5 ms |
2944 KB |
ok, correct split |
46 |
Correct |
4 ms |
2944 KB |
ok, correct split |
47 |
Correct |
4 ms |
2944 KB |
ok, no valid answer |
48 |
Correct |
4 ms |
2944 KB |
ok, correct split |
49 |
Correct |
4 ms |
2944 KB |
ok, correct split |
50 |
Correct |
2 ms |
2688 KB |
ok, no valid answer |
51 |
Correct |
2 ms |
2688 KB |
ok, no valid answer |
52 |
Correct |
3 ms |
2944 KB |
ok, no valid answer |
53 |
Correct |
5 ms |
2944 KB |
ok, no valid answer |
54 |
Correct |
4 ms |
2864 KB |
ok, no valid answer |
55 |
Correct |
4 ms |
2944 KB |
ok, no valid answer |
56 |
Correct |
4 ms |
2944 KB |
ok, no valid answer |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2688 KB |
ok, correct split |
2 |
Correct |
2 ms |
2688 KB |
ok, correct split |
3 |
Correct |
2 ms |
2688 KB |
ok, correct split |
4 |
Correct |
2 ms |
2688 KB |
ok, correct split |
5 |
Correct |
2 ms |
2688 KB |
ok, correct split |
6 |
Correct |
3 ms |
2688 KB |
ok, correct split |
7 |
Correct |
125 ms |
18800 KB |
ok, correct split |
8 |
Correct |
101 ms |
14556 KB |
ok, correct split |
9 |
Correct |
121 ms |
15644 KB |
ok, correct split |
10 |
Correct |
114 ms |
20724 KB |
ok, correct split |
11 |
Correct |
122 ms |
19184 KB |
ok, correct split |
12 |
Correct |
2 ms |
2688 KB |
ok, correct split |
13 |
Correct |
2 ms |
2688 KB |
ok, correct split |
14 |
Correct |
2 ms |
2688 KB |
ok, correct split |
15 |
Correct |
123 ms |
14832 KB |
ok, correct split |
16 |
Correct |
96 ms |
11508 KB |
ok, correct split |
17 |
Correct |
121 ms |
20724 KB |
ok, correct split |
18 |
Correct |
116 ms |
17396 KB |
ok, correct split |
19 |
Correct |
143 ms |
13812 KB |
ok, correct split |
20 |
Correct |
100 ms |
11508 KB |
ok, correct split |
21 |
Correct |
62 ms |
11504 KB |
ok, correct split |
22 |
Correct |
65 ms |
11376 KB |
ok, correct split |
23 |
Correct |
68 ms |
11888 KB |
ok, correct split |
24 |
Correct |
2 ms |
2688 KB |
ok, correct split |
25 |
Correct |
108 ms |
10340 KB |
ok, correct split |
26 |
Correct |
30 ms |
5884 KB |
ok, correct split |
27 |
Correct |
2 ms |
2688 KB |
ok, correct split |
28 |
Correct |
116 ms |
12144 KB |
ok, correct split |
29 |
Correct |
111 ms |
11632 KB |
ok, correct split |
30 |
Correct |
121 ms |
12020 KB |
ok, correct split |
31 |
Correct |
116 ms |
13040 KB |
ok, correct split |
32 |
Correct |
124 ms |
11764 KB |
ok, correct split |
33 |
Correct |
28 ms |
5248 KB |
ok, no valid answer |
34 |
Correct |
42 ms |
6516 KB |
ok, no valid answer |
35 |
Correct |
88 ms |
10224 KB |
ok, no valid answer |
36 |
Correct |
99 ms |
9904 KB |
ok, no valid answer |
37 |
Correct |
70 ms |
10224 KB |
ok, no valid answer |
38 |
Correct |
2 ms |
2688 KB |
ok, correct split |
39 |
Correct |
2 ms |
2688 KB |
ok, no valid answer |
40 |
Correct |
2 ms |
2688 KB |
ok, correct split |
41 |
Correct |
2 ms |
2688 KB |
ok, correct split |
42 |
Correct |
2 ms |
2688 KB |
ok, correct split |
43 |
Correct |
2 ms |
2688 KB |
ok, correct split |
44 |
Correct |
2 ms |
2688 KB |
ok, correct split |
45 |
Correct |
2 ms |
2688 KB |
ok, correct split |
46 |
Correct |
5 ms |
3072 KB |
ok, correct split |
47 |
Correct |
5 ms |
2944 KB |
ok, correct split |
48 |
Correct |
2 ms |
2688 KB |
ok, correct split |
49 |
Correct |
5 ms |
2944 KB |
ok, correct split |
50 |
Correct |
2 ms |
2688 KB |
ok, correct split |
51 |
Correct |
2 ms |
2688 KB |
ok, correct split |
52 |
Correct |
2 ms |
2688 KB |
ok, correct split |
53 |
Correct |
2 ms |
2688 KB |
ok, correct split |
54 |
Correct |
2 ms |
2688 KB |
ok, correct split |
55 |
Correct |
2 ms |
2816 KB |
ok, correct split |
56 |
Correct |
2 ms |
2688 KB |
ok, correct split |
57 |
Correct |
3 ms |
2816 KB |
ok, correct split |
58 |
Correct |
5 ms |
2944 KB |
ok, correct split |
59 |
Correct |
4 ms |
2944 KB |
ok, correct split |
60 |
Correct |
4 ms |
2944 KB |
ok, correct split |
61 |
Correct |
4 ms |
2944 KB |
ok, correct split |
62 |
Correct |
4 ms |
2944 KB |
ok, correct split |
63 |
Correct |
4 ms |
2944 KB |
ok, correct split |
64 |
Correct |
4 ms |
2944 KB |
ok, correct split |
65 |
Correct |
4 ms |
2944 KB |
ok, correct split |
66 |
Correct |
2 ms |
2688 KB |
ok, correct split |
67 |
Correct |
4 ms |
2944 KB |
ok, correct split |
68 |
Correct |
3 ms |
2816 KB |
ok, correct split |
69 |
Correct |
2 ms |
2688 KB |
ok, correct split |
70 |
Correct |
2 ms |
2688 KB |
ok, correct split |
71 |
Correct |
4 ms |
2944 KB |
ok, correct split |
72 |
Correct |
5 ms |
2944 KB |
ok, correct split |
73 |
Correct |
4 ms |
2944 KB |
ok, correct split |
74 |
Correct |
5 ms |
2944 KB |
ok, correct split |
75 |
Correct |
6 ms |
2944 KB |
ok, correct split |
76 |
Correct |
5 ms |
2944 KB |
ok, correct split |
77 |
Correct |
4 ms |
2944 KB |
ok, correct split |
78 |
Correct |
3 ms |
2816 KB |
ok, correct split |
79 |
Correct |
3 ms |
2816 KB |
ok, correct split |
80 |
Correct |
5 ms |
2944 KB |
ok, correct split |
81 |
Correct |
4 ms |
2944 KB |
ok, correct split |
82 |
Correct |
5 ms |
2944 KB |
ok, correct split |
83 |
Correct |
4 ms |
2944 KB |
ok, correct split |
84 |
Correct |
4 ms |
2944 KB |
ok, no valid answer |
85 |
Correct |
4 ms |
2944 KB |
ok, correct split |
86 |
Correct |
4 ms |
2944 KB |
ok, correct split |
87 |
Correct |
2 ms |
2688 KB |
ok, no valid answer |
88 |
Correct |
2 ms |
2688 KB |
ok, no valid answer |
89 |
Correct |
3 ms |
2944 KB |
ok, no valid answer |
90 |
Correct |
5 ms |
2944 KB |
ok, no valid answer |
91 |
Correct |
4 ms |
2864 KB |
ok, no valid answer |
92 |
Correct |
4 ms |
2944 KB |
ok, no valid answer |
93 |
Correct |
4 ms |
2944 KB |
ok, no valid answer |
94 |
Correct |
125 ms |
14832 KB |
ok, correct split |
95 |
Correct |
189 ms |
20464 KB |
ok, correct split |
96 |
Correct |
162 ms |
18416 KB |
ok, correct split |
97 |
Correct |
30 ms |
6272 KB |
ok, correct split |
98 |
Correct |
31 ms |
6400 KB |
ok, correct split |
99 |
Correct |
57 ms |
8828 KB |
ok, correct split |
100 |
Correct |
155 ms |
15448 KB |
ok, correct split |
101 |
Correct |
133 ms |
14192 KB |
ok, correct split |
102 |
Correct |
133 ms |
13552 KB |
ok, correct split |
103 |
Correct |
110 ms |
13424 KB |
ok, correct split |
104 |
Correct |
125 ms |
15072 KB |
ok, correct split |
105 |
Correct |
52 ms |
8276 KB |
ok, correct split |
106 |
Correct |
129 ms |
15328 KB |
ok, correct split |
107 |
Correct |
99 ms |
11500 KB |
ok, correct split |
108 |
Correct |
96 ms |
11504 KB |
ok, correct split |
109 |
Correct |
162 ms |
14880 KB |
ok, correct split |
110 |
Correct |
147 ms |
14960 KB |
ok, correct split |
111 |
Correct |
158 ms |
14960 KB |
ok, correct split |
112 |
Correct |
146 ms |
15164 KB |
ok, correct split |
113 |
Correct |
140 ms |
15216 KB |
ok, correct split |
114 |
Correct |
14 ms |
4352 KB |
ok, correct split |
115 |
Correct |
13 ms |
4096 KB |
ok, correct split |
116 |
Correct |
136 ms |
14460 KB |
ok, correct split |
117 |
Correct |
138 ms |
14480 KB |
ok, correct split |
118 |
Correct |
116 ms |
11508 KB |
ok, correct split |
119 |
Correct |
95 ms |
11512 KB |
ok, correct split |
120 |
Correct |
115 ms |
14960 KB |
ok, correct split |
121 |
Correct |
101 ms |
11248 KB |
ok, no valid answer |
122 |
Correct |
97 ms |
11120 KB |
ok, no valid answer |
123 |
Correct |
172 ms |
15092 KB |
ok, no valid answer |
124 |
Correct |
177 ms |
15092 KB |
ok, no valid answer |
125 |
Correct |
102 ms |
12276 KB |
ok, no valid answer |
126 |
Correct |
65 ms |
10480 KB |
ok, no valid answer |
127 |
Correct |
115 ms |
12784 KB |
ok, no valid answer |