#include "split.h"
#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define f first
#define s second
const int N = 1e5 + 5;
int sz[N], f[N], p[N], bl[N], h[N];
vector<int> V[N], adj[N], eb[N];
vector<int> ans, b(4);
vector<pii> x;
void dfs(int u, int P) {
f[u] = 1;
p[u] = P;
h[u] = h[P] + 1;
for(int i = 0; i < V[u].size(); i++) {
if(f[V[u][i]]) {
eb[u].push_back(V[u][i]);
continue;
}
dfs(V[u][i], u);
adj[u].push_back(V[u][i]);
sz[u] += sz[V[u][i]];
}
++sz[u];
}
void dfs2(int u, int P) {
int F = 0;
for(int i = 0; i < eb[u].size();i++) {
if(h[eb[u][i]] < h[P]) {
F = 1;
x.push_back({u, sz[u]});
break;
}
}
if(F) return;
for(int i = 0; i < adj[u].size(); i++) {
dfs2(adj[u][i], P);
}
}
void dfs3(int u, int t) {
if(!b[t]) return;
--b[t];
ans[u] = t;
f[u] = 1;
for(int i = 0; i < adj[u].size(); i++) {
if(bl[adj[u][i]]) continue;
if(!b[t]) return;
dfs3(adj[u][i], t);
}
}
void dfs4(int u, int t) {
if(!b[t]) return;
--b[t];
ans[u] = t;
f[u] = 1;
for(int i = 0; i < V[u].size(); i++) {
if(f[V[u][i]]) continue;
if(!b[t]) return;
dfs4(V[u][i], t);
}
}
int get(vector<int> x, int t) {
pii mn;
mn = {N, 5};
for(int i = 1; i <= 3; i++) {
if(i == t) continue;
mn = min(mn, {x[i], i});
}
return mn.s;
}
vector<int> find_split(int n, int A, int B, int C, vector<int> P, vector<int> q) {
ans.resize(n);
int a = min(A, min(B, C));
b[1] = A, b[2] = B, b[3] = C;//cout << "+" << endl;
for(int i = 0; i < P.size(); i++) {
int u = P[i], v = q[i];
V[u].push_back(v);
V[v].push_back(u);
}
dfs(0, 0);
for(int i = 0; i < n; i++) {
if(sz[i] < a) continue;
int F = 0;
for(int j = 0; j < adj[i].size(); j++) {
if(sz[adj[i][j]] >= a) {
F = 1;
break;
}
}
if(F) continue;
if(!i) return ans;
x.clear();
for(int j = 0; j < adj[i].size(); j++) {
dfs2(adj[i][j], i);
}
int oth = n - sz[i];
while(oth < a) {
if(!x.size()) break;
oth += x.back().s;
bl[x.back().f] = 1;
x.pop_back();
}
if(oth < a) return ans;
int t1 = get(b, 0), t2 = get(b, t1);
for(int j = 0; j < n; j++) f[j] = 0;
int bbb = b[t2];
dfs3(i, (oth >= bbb ? t1 : t2));
dfs4(p[i], (oth < bbb ? t1 : t2)); assert(!b[t2]&&!b[t1]);
for(int j = 0; j < n; j++) if(!ans[j]) ans[j] = 6 - t1 - t2;
return ans;
}
return ans;
}
Compilation message
split.cpp: In function 'void dfs(int, int)':
split.cpp:16:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
16 | for(int i = 0; i < V[u].size(); i++) {
| ~~^~~~~~~~~~~~~
split.cpp: In function 'void dfs2(int, int)':
split.cpp:29:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
29 | for(int i = 0; i < eb[u].size();i++) {
| ~~^~~~~~~~~~~~~~
split.cpp:37:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
37 | for(int i = 0; i < adj[u].size(); i++) {
| ~~^~~~~~~~~~~~~~~
split.cpp: In function 'void dfs3(int, int)':
split.cpp:46:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
46 | for(int i = 0; i < adj[u].size(); i++) {
| ~~^~~~~~~~~~~~~~~
split.cpp: In function 'void dfs4(int, int)':
split.cpp:57:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
57 | for(int i = 0; i < V[u].size(); i++) {
| ~~^~~~~~~~~~~~~
split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:76:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
76 | for(int i = 0; i < P.size(); i++) {
| ~~^~~~~~~~~~
split.cpp:86:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
86 | for(int j = 0; j < adj[i].size(); j++) {
| ~~^~~~~~~~~~~~~~~
split.cpp:95:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
95 | for(int j = 0; j < adj[i].size(); j++) {
| ~~^~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
7252 KB |
ok, correct split |
2 |
Correct |
4 ms |
7264 KB |
ok, correct split |
3 |
Correct |
4 ms |
7252 KB |
ok, correct split |
4 |
Correct |
4 ms |
7252 KB |
ok, correct split |
5 |
Correct |
4 ms |
7380 KB |
ok, correct split |
6 |
Correct |
4 ms |
7380 KB |
ok, correct split |
7 |
Correct |
108 ms |
29520 KB |
ok, correct split |
8 |
Correct |
102 ms |
27076 KB |
ok, correct split |
9 |
Correct |
99 ms |
25924 KB |
ok, correct split |
10 |
Correct |
94 ms |
30036 KB |
ok, correct split |
11 |
Correct |
133 ms |
30032 KB |
ok, correct split |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
7252 KB |
ok, correct split |
2 |
Correct |
4 ms |
7252 KB |
ok, correct split |
3 |
Correct |
3 ms |
7252 KB |
ok, correct split |
4 |
Correct |
111 ms |
25104 KB |
ok, correct split |
5 |
Correct |
82 ms |
19220 KB |
ok, correct split |
6 |
Correct |
96 ms |
29940 KB |
ok, correct split |
7 |
Correct |
118 ms |
26572 KB |
ok, correct split |
8 |
Correct |
127 ms |
22100 KB |
ok, correct split |
9 |
Correct |
101 ms |
20684 KB |
ok, correct split |
10 |
Correct |
79 ms |
18260 KB |
ok, correct split |
11 |
Correct |
61 ms |
18200 KB |
ok, correct split |
12 |
Correct |
57 ms |
18244 KB |
ok, correct split |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
7252 KB |
ok, correct split |
2 |
Correct |
121 ms |
19240 KB |
ok, correct split |
3 |
Correct |
30 ms |
12116 KB |
ok, correct split |
4 |
Correct |
4 ms |
7252 KB |
ok, correct split |
5 |
Correct |
103 ms |
23664 KB |
ok, correct split |
6 |
Correct |
106 ms |
23404 KB |
ok, correct split |
7 |
Correct |
105 ms |
23160 KB |
ok, correct split |
8 |
Correct |
112 ms |
24860 KB |
ok, correct split |
9 |
Correct |
104 ms |
22976 KB |
ok, correct split |
10 |
Correct |
27 ms |
11212 KB |
ok, no valid answer |
11 |
Correct |
37 ms |
13288 KB |
ok, no valid answer |
12 |
Correct |
72 ms |
18680 KB |
ok, no valid answer |
13 |
Correct |
90 ms |
19068 KB |
ok, no valid answer |
14 |
Correct |
66 ms |
18244 KB |
ok, no valid answer |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
7344 KB |
ok, correct split |
2 |
Correct |
5 ms |
7252 KB |
ok, no valid answer |
3 |
Correct |
4 ms |
7252 KB |
ok, correct split |
4 |
Correct |
4 ms |
7252 KB |
ok, correct split |
5 |
Correct |
4 ms |
7252 KB |
ok, correct split |
6 |
Correct |
4 ms |
7252 KB |
ok, correct split |
7 |
Correct |
4 ms |
7252 KB |
ok, correct split |
8 |
Correct |
3 ms |
7252 KB |
ok, correct split |
9 |
Correct |
6 ms |
7764 KB |
ok, correct split |
10 |
Correct |
7 ms |
7636 KB |
ok, correct split |
11 |
Correct |
4 ms |
7380 KB |
ok, correct split |
12 |
Correct |
6 ms |
7636 KB |
ok, correct split |
13 |
Correct |
3 ms |
7252 KB |
ok, correct split |
14 |
Correct |
6 ms |
7332 KB |
ok, correct split |
15 |
Correct |
4 ms |
7380 KB |
ok, correct split |
16 |
Correct |
5 ms |
7252 KB |
ok, correct split |
17 |
Correct |
4 ms |
7252 KB |
ok, correct split |
18 |
Correct |
4 ms |
7252 KB |
ok, correct split |
19 |
Correct |
4 ms |
7380 KB |
ok, correct split |
20 |
Correct |
5 ms |
7496 KB |
ok, correct split |
21 |
Correct |
5 ms |
7764 KB |
ok, correct split |
22 |
Correct |
5 ms |
7636 KB |
ok, correct split |
23 |
Correct |
5 ms |
7764 KB |
ok, correct split |
24 |
Correct |
5 ms |
7764 KB |
ok, correct split |
25 |
Correct |
5 ms |
7764 KB |
ok, correct split |
26 |
Correct |
5 ms |
7764 KB |
ok, correct split |
27 |
Correct |
6 ms |
7764 KB |
ok, correct split |
28 |
Correct |
5 ms |
7744 KB |
ok, correct split |
29 |
Correct |
4 ms |
7380 KB |
ok, correct split |
30 |
Correct |
6 ms |
7764 KB |
ok, correct split |
31 |
Correct |
6 ms |
7380 KB |
ok, correct split |
32 |
Correct |
5 ms |
7380 KB |
ok, correct split |
33 |
Correct |
5 ms |
7380 KB |
ok, correct split |
34 |
Correct |
6 ms |
7680 KB |
ok, correct split |
35 |
Correct |
6 ms |
7624 KB |
ok, correct split |
36 |
Correct |
5 ms |
7636 KB |
ok, correct split |
37 |
Correct |
6 ms |
7764 KB |
ok, correct split |
38 |
Correct |
6 ms |
7764 KB |
ok, correct split |
39 |
Correct |
6 ms |
7764 KB |
ok, correct split |
40 |
Correct |
6 ms |
7752 KB |
ok, correct split |
41 |
Correct |
6 ms |
7536 KB |
ok, correct split |
42 |
Correct |
5 ms |
7496 KB |
ok, correct split |
43 |
Correct |
6 ms |
7764 KB |
ok, correct split |
44 |
Correct |
6 ms |
7752 KB |
ok, correct split |
45 |
Correct |
6 ms |
7764 KB |
ok, correct split |
46 |
Correct |
5 ms |
7764 KB |
ok, correct split |
47 |
Correct |
5 ms |
7764 KB |
ok, no valid answer |
48 |
Correct |
5 ms |
7636 KB |
ok, correct split |
49 |
Correct |
6 ms |
7764 KB |
ok, correct split |
50 |
Correct |
4 ms |
7252 KB |
ok, no valid answer |
51 |
Correct |
4 ms |
7252 KB |
ok, no valid answer |
52 |
Correct |
5 ms |
7636 KB |
ok, no valid answer |
53 |
Correct |
6 ms |
7752 KB |
ok, no valid answer |
54 |
Correct |
5 ms |
7628 KB |
ok, no valid answer |
55 |
Correct |
5 ms |
7636 KB |
ok, no valid answer |
56 |
Correct |
5 ms |
7636 KB |
ok, no valid answer |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
7252 KB |
ok, correct split |
2 |
Correct |
4 ms |
7264 KB |
ok, correct split |
3 |
Correct |
4 ms |
7252 KB |
ok, correct split |
4 |
Correct |
4 ms |
7252 KB |
ok, correct split |
5 |
Correct |
4 ms |
7380 KB |
ok, correct split |
6 |
Correct |
4 ms |
7380 KB |
ok, correct split |
7 |
Correct |
108 ms |
29520 KB |
ok, correct split |
8 |
Correct |
102 ms |
27076 KB |
ok, correct split |
9 |
Correct |
99 ms |
25924 KB |
ok, correct split |
10 |
Correct |
94 ms |
30036 KB |
ok, correct split |
11 |
Correct |
133 ms |
30032 KB |
ok, correct split |
12 |
Correct |
4 ms |
7252 KB |
ok, correct split |
13 |
Correct |
4 ms |
7252 KB |
ok, correct split |
14 |
Correct |
3 ms |
7252 KB |
ok, correct split |
15 |
Correct |
111 ms |
25104 KB |
ok, correct split |
16 |
Correct |
82 ms |
19220 KB |
ok, correct split |
17 |
Correct |
96 ms |
29940 KB |
ok, correct split |
18 |
Correct |
118 ms |
26572 KB |
ok, correct split |
19 |
Correct |
127 ms |
22100 KB |
ok, correct split |
20 |
Correct |
101 ms |
20684 KB |
ok, correct split |
21 |
Correct |
79 ms |
18260 KB |
ok, correct split |
22 |
Correct |
61 ms |
18200 KB |
ok, correct split |
23 |
Correct |
57 ms |
18244 KB |
ok, correct split |
24 |
Correct |
4 ms |
7252 KB |
ok, correct split |
25 |
Correct |
121 ms |
19240 KB |
ok, correct split |
26 |
Correct |
30 ms |
12116 KB |
ok, correct split |
27 |
Correct |
4 ms |
7252 KB |
ok, correct split |
28 |
Correct |
103 ms |
23664 KB |
ok, correct split |
29 |
Correct |
106 ms |
23404 KB |
ok, correct split |
30 |
Correct |
105 ms |
23160 KB |
ok, correct split |
31 |
Correct |
112 ms |
24860 KB |
ok, correct split |
32 |
Correct |
104 ms |
22976 KB |
ok, correct split |
33 |
Correct |
27 ms |
11212 KB |
ok, no valid answer |
34 |
Correct |
37 ms |
13288 KB |
ok, no valid answer |
35 |
Correct |
72 ms |
18680 KB |
ok, no valid answer |
36 |
Correct |
90 ms |
19068 KB |
ok, no valid answer |
37 |
Correct |
66 ms |
18244 KB |
ok, no valid answer |
38 |
Correct |
4 ms |
7344 KB |
ok, correct split |
39 |
Correct |
5 ms |
7252 KB |
ok, no valid answer |
40 |
Correct |
4 ms |
7252 KB |
ok, correct split |
41 |
Correct |
4 ms |
7252 KB |
ok, correct split |
42 |
Correct |
4 ms |
7252 KB |
ok, correct split |
43 |
Correct |
4 ms |
7252 KB |
ok, correct split |
44 |
Correct |
4 ms |
7252 KB |
ok, correct split |
45 |
Correct |
3 ms |
7252 KB |
ok, correct split |
46 |
Correct |
6 ms |
7764 KB |
ok, correct split |
47 |
Correct |
7 ms |
7636 KB |
ok, correct split |
48 |
Correct |
4 ms |
7380 KB |
ok, correct split |
49 |
Correct |
6 ms |
7636 KB |
ok, correct split |
50 |
Correct |
3 ms |
7252 KB |
ok, correct split |
51 |
Correct |
6 ms |
7332 KB |
ok, correct split |
52 |
Correct |
4 ms |
7380 KB |
ok, correct split |
53 |
Correct |
5 ms |
7252 KB |
ok, correct split |
54 |
Correct |
4 ms |
7252 KB |
ok, correct split |
55 |
Correct |
4 ms |
7252 KB |
ok, correct split |
56 |
Correct |
4 ms |
7380 KB |
ok, correct split |
57 |
Correct |
5 ms |
7496 KB |
ok, correct split |
58 |
Correct |
5 ms |
7764 KB |
ok, correct split |
59 |
Correct |
5 ms |
7636 KB |
ok, correct split |
60 |
Correct |
5 ms |
7764 KB |
ok, correct split |
61 |
Correct |
5 ms |
7764 KB |
ok, correct split |
62 |
Correct |
5 ms |
7764 KB |
ok, correct split |
63 |
Correct |
5 ms |
7764 KB |
ok, correct split |
64 |
Correct |
6 ms |
7764 KB |
ok, correct split |
65 |
Correct |
5 ms |
7744 KB |
ok, correct split |
66 |
Correct |
4 ms |
7380 KB |
ok, correct split |
67 |
Correct |
6 ms |
7764 KB |
ok, correct split |
68 |
Correct |
6 ms |
7380 KB |
ok, correct split |
69 |
Correct |
5 ms |
7380 KB |
ok, correct split |
70 |
Correct |
5 ms |
7380 KB |
ok, correct split |
71 |
Correct |
6 ms |
7680 KB |
ok, correct split |
72 |
Correct |
6 ms |
7624 KB |
ok, correct split |
73 |
Correct |
5 ms |
7636 KB |
ok, correct split |
74 |
Correct |
6 ms |
7764 KB |
ok, correct split |
75 |
Correct |
6 ms |
7764 KB |
ok, correct split |
76 |
Correct |
6 ms |
7764 KB |
ok, correct split |
77 |
Correct |
6 ms |
7752 KB |
ok, correct split |
78 |
Correct |
6 ms |
7536 KB |
ok, correct split |
79 |
Correct |
5 ms |
7496 KB |
ok, correct split |
80 |
Correct |
6 ms |
7764 KB |
ok, correct split |
81 |
Correct |
6 ms |
7752 KB |
ok, correct split |
82 |
Correct |
6 ms |
7764 KB |
ok, correct split |
83 |
Correct |
5 ms |
7764 KB |
ok, correct split |
84 |
Correct |
5 ms |
7764 KB |
ok, no valid answer |
85 |
Correct |
5 ms |
7636 KB |
ok, correct split |
86 |
Correct |
6 ms |
7764 KB |
ok, correct split |
87 |
Correct |
4 ms |
7252 KB |
ok, no valid answer |
88 |
Correct |
4 ms |
7252 KB |
ok, no valid answer |
89 |
Correct |
5 ms |
7636 KB |
ok, no valid answer |
90 |
Correct |
6 ms |
7752 KB |
ok, no valid answer |
91 |
Correct |
5 ms |
7628 KB |
ok, no valid answer |
92 |
Correct |
5 ms |
7636 KB |
ok, no valid answer |
93 |
Correct |
5 ms |
7636 KB |
ok, no valid answer |
94 |
Correct |
120 ms |
23944 KB |
ok, correct split |
95 |
Correct |
159 ms |
30284 KB |
ok, correct split |
96 |
Correct |
144 ms |
28252 KB |
ok, correct split |
97 |
Correct |
30 ms |
12584 KB |
ok, correct split |
98 |
Correct |
30 ms |
12772 KB |
ok, correct split |
99 |
Correct |
50 ms |
15560 KB |
ok, correct split |
100 |
Correct |
144 ms |
25036 KB |
ok, correct split |
101 |
Correct |
113 ms |
23608 KB |
ok, correct split |
102 |
Correct |
126 ms |
23364 KB |
ok, correct split |
103 |
Correct |
112 ms |
22708 KB |
ok, correct split |
104 |
Correct |
95 ms |
23408 KB |
ok, correct split |
105 |
Correct |
59 ms |
15700 KB |
ok, correct split |
106 |
Correct |
98 ms |
24000 KB |
ok, correct split |
107 |
Correct |
87 ms |
20796 KB |
ok, correct split |
108 |
Correct |
85 ms |
20508 KB |
ok, correct split |
109 |
Correct |
148 ms |
24828 KB |
ok, correct split |
110 |
Correct |
141 ms |
25820 KB |
ok, correct split |
111 |
Correct |
135 ms |
25680 KB |
ok, correct split |
112 |
Correct |
122 ms |
24528 KB |
ok, correct split |
113 |
Correct |
135 ms |
24216 KB |
ok, correct split |
114 |
Correct |
14 ms |
9428 KB |
ok, correct split |
115 |
Correct |
15 ms |
9172 KB |
ok, correct split |
116 |
Correct |
118 ms |
25412 KB |
ok, correct split |
117 |
Correct |
134 ms |
25352 KB |
ok, correct split |
118 |
Correct |
99 ms |
21952 KB |
ok, correct split |
119 |
Correct |
94 ms |
21820 KB |
ok, correct split |
120 |
Correct |
129 ms |
26780 KB |
ok, correct split |
121 |
Correct |
82 ms |
20424 KB |
ok, no valid answer |
122 |
Correct |
80 ms |
20172 KB |
ok, no valid answer |
123 |
Correct |
138 ms |
25380 KB |
ok, no valid answer |
124 |
Correct |
137 ms |
25040 KB |
ok, no valid answer |
125 |
Correct |
80 ms |
21052 KB |
ok, no valid answer |
126 |
Correct |
68 ms |
18244 KB |
ok, no valid answer |
127 |
Correct |
106 ms |
22284 KB |
ok, no valid answer |