#include "split.h"
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vim;
vim V[100010], W[100010];
vim C[100010], par;
int chk[100010];
pair<int,int> pi[3];
int N, Ctd;
vim ans;
int chkans[100010];
void mst(int lev)
{
chk[lev]=1;
for (int i:V[lev]) {
if (!chk[i]) {
par[i]=lev;
C[lev].push_back(i);
mst(i);
}
}
}
int cent(int lev)
{
vector<int> Cs;
for (int i:C[lev]) {
Cs.push_back(cent(i));
}
int ret=0, flag=0;
for (int i:Cs) {
ret+=i;
if (i>N/2) flag=1;
}
if (N-ret-1>N/2) flag=1;
if (!flag) Ctd=lev;
return ret+1;
}
void dfs(int lev)
{
chk[lev]=1;
for (int i:C[lev]) {
if (!chk[i]) {
W[lev].push_back(i);
W[i].push_back(lev);
dfs(i);
}
}
if (!chk[par[lev]]) {
W[lev].push_back(par[lev]);
W[par[lev]].push_back(lev);
dfs(par[lev]);
}
}
int gC(int lev){
chk[lev]=1;
int ret=0;
for (int i:W[lev]) {
if (!chk[i]) ret+=gC(i);
}
return ret+1;
}
void GA1(int st, int sw)
{
if (sw==0) {
if (!pi[0].first) return ;
chk[st]=1;
chkans[st]=pi[0].second+1;
pi[0].first--;
for (int i:W[st]) {
if (!chk[i]) {
GA1(i, sw);
}
}
}
if (sw==1) {
if (!pi[1].first) return ;
chk[st]=1;
chkans[st]=pi[1].second+1;
pi[1].first--;
for (int i:W[st]) {
if (!chk[i]) {
GA1(i, sw);
}
}
}
if (sw==2) {
for (int i=0; i<N; i++) if (!chkans[i]) chkans[i]=pi[2].second+1;
for (int i=0; i<N; i++) ans.push_back(chkans[i]);
}
}
int dfs1(int lev)
{
chk[lev]=1;
int ret=1;
for (int i:V[lev]) {
if (!chk[i]) {
ret+=dfs1(i);
}
}
return ret;
}
void dfs2(int lev)
{
if (!pi[0].first) return ;
chk[lev]=1;
chkans[lev]=pi[0].second;
pi[0].first--;
for (int i:V[lev]) {
if (!chk[i]&&i!=Ctd) dfs2(i);
}
}
void dfs3(int lev)
{
if (!pi[1].first) return ;
chk[lev]=1;
chkans[lev]=pi[1].second;
pi[1].first--;
for (int i:V[lev]) {
if (!chk[i]) dfs3(i);
}
}
void dfs4()
{
int i, j=0;
for (i=0; i<N; i++) {if (!chk[i]) {chkans[i]=pi[2].second; j++;}}
for (i=0; i<N; i++) ans.push_back(chkans[i]+1);
if (j!=pi[2].first) {
printf("%d", 1/0);
}
}
int GA2()
{
int i, ret, fl=0;
memset(chk, 0, sizeof(chk));
chk[Ctd]=1;
for (i=0; i<N; i++) {
if (i!=Ctd&&!chk[i]) {
ret=dfs1(i);
if (ret>=pi[0].first) {
memset(chk, 0, sizeof(chk));
dfs2(i);
dfs3(Ctd);
dfs4();
fl=1;
break;
}
}
}
if (!fl) return -1;
return 0;
}
vim IMPOSSIBLE()
{
vim ret;
for (int i=0; i<N; i++) ret.push_back(0);
//if (ret.size()!=N) assert(false);
return ret;
}
vim find_split(int n, int a, int b, int c, vim p, vim q) {
N=n;
par.resize(n);
pi[0]={a,0}; pi[1]={b,1}; pi[2]={c,2};
sort(pi,pi+3);
int i;
for (i=0; i<p.size(); i++) {
V[p[i]].push_back(q[i]);
V[q[i]].push_back(p[i]);
}
mst(0);
cent(0);
memset(chk, 0, sizeof(chk));
dfs(Ctd);
memset(chk, 0, sizeof(chk));
chk[Ctd]=1;
vim CtdV;
for (int j:W[Ctd]) CtdV.push_back(gC(j));
memset(chk, 0, sizeof(chk));
chk[Ctd]=1;
for (i=0; i<CtdV.size(); i++) {
if (CtdV[i]>=pi[0].first){
GA1(W[Ctd][i], 0);
GA1(Ctd, 1);
GA1(0, 2);
if (ans.size()!=N) assert(false);
return ans;
}
}
if (GA2()==-1) {
return IMPOSSIBLE();
}
else {
//if (ans.size()!=N) assert(false);
return ans;
}
}
Compilation message
split.cpp: In function 'void dfs4()':
split.cpp:128:17: warning: division by zero [-Wdiv-by-zero]
printf("%d", 1/0);
~^~
split.cpp: In function 'vim find_split(int, int, int, int, vim, vim)':
split.cpp:166:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (i=0; i<p.size(); i++) {
~^~~~~~~~~
split.cpp:180:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (i=0; i<CtdV.size(); i++) {
~^~~~~~~~~~~~
split.cpp:185:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (ans.size()!=N) assert(false);
~~~~~~~~~~^~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
8 ms |
7800 KB |
ok, correct split |
2 |
Correct |
9 ms |
7800 KB |
ok, correct split |
3 |
Correct |
9 ms |
7800 KB |
ok, correct split |
4 |
Correct |
9 ms |
7800 KB |
ok, correct split |
5 |
Correct |
9 ms |
7800 KB |
ok, correct split |
6 |
Correct |
9 ms |
7800 KB |
ok, correct split |
7 |
Correct |
186 ms |
27888 KB |
ok, correct split |
8 |
Correct |
175 ms |
25824 KB |
ok, correct split |
9 |
Correct |
188 ms |
24944 KB |
ok, correct split |
10 |
Correct |
207 ms |
28400 KB |
ok, correct split |
11 |
Correct |
193 ms |
28272 KB |
ok, correct split |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
8 ms |
7804 KB |
ok, correct split |
2 |
Correct |
9 ms |
7800 KB |
ok, correct split |
3 |
Correct |
8 ms |
7676 KB |
ok, correct split |
4 |
Correct |
202 ms |
24196 KB |
ok, correct split |
5 |
Correct |
156 ms |
19184 KB |
ok, correct split |
6 |
Correct |
190 ms |
28276 KB |
ok, correct split |
7 |
Correct |
183 ms |
25328 KB |
ok, correct split |
8 |
Correct |
219 ms |
21724 KB |
ok, correct split |
9 |
Correct |
152 ms |
20464 KB |
ok, correct split |
10 |
Correct |
101 ms |
18920 KB |
ok, correct split |
11 |
Correct |
101 ms |
18920 KB |
ok, correct split |
12 |
Correct |
99 ms |
18892 KB |
ok, correct split |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
8 ms |
7736 KB |
ok, correct split |
2 |
Correct |
163 ms |
19160 KB |
ok, correct split |
3 |
Correct |
59 ms |
12404 KB |
ok, correct split |
4 |
Correct |
9 ms |
7800 KB |
ok, correct split |
5 |
Correct |
181 ms |
23016 KB |
ok, correct split |
6 |
Correct |
206 ms |
22740 KB |
ok, correct split |
7 |
Correct |
238 ms |
22552 KB |
ok, correct split |
8 |
Correct |
183 ms |
23920 KB |
ok, correct split |
9 |
Correct |
193 ms |
22444 KB |
ok, correct split |
10 |
Correct |
49 ms |
11512 KB |
ok, no valid answer |
11 |
Correct |
72 ms |
13160 KB |
ok, no valid answer |
12 |
Correct |
128 ms |
18568 KB |
ok, no valid answer |
13 |
Correct |
170 ms |
18568 KB |
ok, no valid answer |
14 |
Correct |
103 ms |
18588 KB |
ok, no valid answer |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
8 ms |
7800 KB |
ok, correct split |
2 |
Correct |
9 ms |
7804 KB |
ok, no valid answer |
3 |
Correct |
9 ms |
7800 KB |
ok, correct split |
4 |
Correct |
9 ms |
7800 KB |
ok, correct split |
5 |
Correct |
9 ms |
7800 KB |
ok, correct split |
6 |
Correct |
9 ms |
7800 KB |
ok, correct split |
7 |
Correct |
9 ms |
7800 KB |
ok, correct split |
8 |
Correct |
9 ms |
7800 KB |
ok, correct split |
9 |
Correct |
12 ms |
8056 KB |
ok, correct split |
10 |
Correct |
12 ms |
8116 KB |
ok, correct split |
11 |
Correct |
9 ms |
7800 KB |
ok, correct split |
12 |
Correct |
12 ms |
8056 KB |
ok, correct split |
13 |
Correct |
9 ms |
7800 KB |
ok, correct split |
14 |
Correct |
9 ms |
7800 KB |
ok, correct split |
15 |
Correct |
8 ms |
7800 KB |
ok, correct split |
16 |
Correct |
9 ms |
7800 KB |
ok, correct split |
17 |
Correct |
8 ms |
7800 KB |
ok, correct split |
18 |
Correct |
9 ms |
7800 KB |
ok, correct split |
19 |
Correct |
9 ms |
7800 KB |
ok, correct split |
20 |
Correct |
10 ms |
7900 KB |
ok, correct split |
21 |
Correct |
11 ms |
8232 KB |
ok, correct split |
22 |
Correct |
11 ms |
8056 KB |
ok, correct split |
23 |
Correct |
11 ms |
8184 KB |
ok, correct split |
24 |
Correct |
12 ms |
8184 KB |
ok, correct split |
25 |
Correct |
13 ms |
8184 KB |
ok, correct split |
26 |
Correct |
11 ms |
8032 KB |
ok, correct split |
27 |
Correct |
12 ms |
8184 KB |
ok, correct split |
28 |
Correct |
11 ms |
8184 KB |
ok, correct split |
29 |
Correct |
9 ms |
7800 KB |
ok, correct split |
30 |
Correct |
12 ms |
8184 KB |
ok, correct split |
31 |
Correct |
9 ms |
7928 KB |
ok, correct split |
32 |
Correct |
9 ms |
7772 KB |
ok, correct split |
33 |
Correct |
9 ms |
7800 KB |
ok, correct split |
34 |
Correct |
12 ms |
8056 KB |
ok, correct split |
35 |
Correct |
12 ms |
8056 KB |
ok, correct split |
36 |
Correct |
11 ms |
8056 KB |
ok, correct split |
37 |
Correct |
13 ms |
8184 KB |
ok, correct split |
38 |
Correct |
12 ms |
8156 KB |
ok, correct split |
39 |
Correct |
12 ms |
8184 KB |
ok, correct split |
40 |
Correct |
12 ms |
8188 KB |
ok, correct split |
41 |
Correct |
10 ms |
7928 KB |
ok, correct split |
42 |
Correct |
10 ms |
7928 KB |
ok, correct split |
43 |
Correct |
14 ms |
8184 KB |
ok, correct split |
44 |
Correct |
12 ms |
8184 KB |
ok, correct split |
45 |
Correct |
14 ms |
8184 KB |
ok, correct split |
46 |
Correct |
13 ms |
8184 KB |
ok, correct split |
47 |
Correct |
11 ms |
8188 KB |
ok, no valid answer |
48 |
Correct |
11 ms |
8056 KB |
ok, correct split |
49 |
Correct |
11 ms |
8184 KB |
ok, correct split |
50 |
Correct |
9 ms |
7800 KB |
ok, no valid answer |
51 |
Correct |
9 ms |
7800 KB |
ok, no valid answer |
52 |
Correct |
11 ms |
8056 KB |
ok, no valid answer |
53 |
Correct |
12 ms |
8184 KB |
ok, no valid answer |
54 |
Correct |
10 ms |
8056 KB |
ok, no valid answer |
55 |
Correct |
11 ms |
8184 KB |
ok, no valid answer |
56 |
Correct |
11 ms |
8184 KB |
ok, no valid answer |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
8 ms |
7800 KB |
ok, correct split |
2 |
Correct |
9 ms |
7800 KB |
ok, correct split |
3 |
Correct |
9 ms |
7800 KB |
ok, correct split |
4 |
Correct |
9 ms |
7800 KB |
ok, correct split |
5 |
Correct |
9 ms |
7800 KB |
ok, correct split |
6 |
Correct |
9 ms |
7800 KB |
ok, correct split |
7 |
Correct |
186 ms |
27888 KB |
ok, correct split |
8 |
Correct |
175 ms |
25824 KB |
ok, correct split |
9 |
Correct |
188 ms |
24944 KB |
ok, correct split |
10 |
Correct |
207 ms |
28400 KB |
ok, correct split |
11 |
Correct |
193 ms |
28272 KB |
ok, correct split |
12 |
Correct |
8 ms |
7804 KB |
ok, correct split |
13 |
Correct |
9 ms |
7800 KB |
ok, correct split |
14 |
Correct |
8 ms |
7676 KB |
ok, correct split |
15 |
Correct |
202 ms |
24196 KB |
ok, correct split |
16 |
Correct |
156 ms |
19184 KB |
ok, correct split |
17 |
Correct |
190 ms |
28276 KB |
ok, correct split |
18 |
Correct |
183 ms |
25328 KB |
ok, correct split |
19 |
Correct |
219 ms |
21724 KB |
ok, correct split |
20 |
Correct |
152 ms |
20464 KB |
ok, correct split |
21 |
Correct |
101 ms |
18920 KB |
ok, correct split |
22 |
Correct |
101 ms |
18920 KB |
ok, correct split |
23 |
Correct |
99 ms |
18892 KB |
ok, correct split |
24 |
Correct |
8 ms |
7736 KB |
ok, correct split |
25 |
Correct |
163 ms |
19160 KB |
ok, correct split |
26 |
Correct |
59 ms |
12404 KB |
ok, correct split |
27 |
Correct |
9 ms |
7800 KB |
ok, correct split |
28 |
Correct |
181 ms |
23016 KB |
ok, correct split |
29 |
Correct |
206 ms |
22740 KB |
ok, correct split |
30 |
Correct |
238 ms |
22552 KB |
ok, correct split |
31 |
Correct |
183 ms |
23920 KB |
ok, correct split |
32 |
Correct |
193 ms |
22444 KB |
ok, correct split |
33 |
Correct |
49 ms |
11512 KB |
ok, no valid answer |
34 |
Correct |
72 ms |
13160 KB |
ok, no valid answer |
35 |
Correct |
128 ms |
18568 KB |
ok, no valid answer |
36 |
Correct |
170 ms |
18568 KB |
ok, no valid answer |
37 |
Correct |
103 ms |
18588 KB |
ok, no valid answer |
38 |
Correct |
8 ms |
7800 KB |
ok, correct split |
39 |
Correct |
9 ms |
7804 KB |
ok, no valid answer |
40 |
Correct |
9 ms |
7800 KB |
ok, correct split |
41 |
Correct |
9 ms |
7800 KB |
ok, correct split |
42 |
Correct |
9 ms |
7800 KB |
ok, correct split |
43 |
Correct |
9 ms |
7800 KB |
ok, correct split |
44 |
Correct |
9 ms |
7800 KB |
ok, correct split |
45 |
Correct |
9 ms |
7800 KB |
ok, correct split |
46 |
Correct |
12 ms |
8056 KB |
ok, correct split |
47 |
Correct |
12 ms |
8116 KB |
ok, correct split |
48 |
Correct |
9 ms |
7800 KB |
ok, correct split |
49 |
Correct |
12 ms |
8056 KB |
ok, correct split |
50 |
Correct |
9 ms |
7800 KB |
ok, correct split |
51 |
Correct |
9 ms |
7800 KB |
ok, correct split |
52 |
Correct |
8 ms |
7800 KB |
ok, correct split |
53 |
Correct |
9 ms |
7800 KB |
ok, correct split |
54 |
Correct |
8 ms |
7800 KB |
ok, correct split |
55 |
Correct |
9 ms |
7800 KB |
ok, correct split |
56 |
Correct |
9 ms |
7800 KB |
ok, correct split |
57 |
Correct |
10 ms |
7900 KB |
ok, correct split |
58 |
Correct |
11 ms |
8232 KB |
ok, correct split |
59 |
Correct |
11 ms |
8056 KB |
ok, correct split |
60 |
Correct |
11 ms |
8184 KB |
ok, correct split |
61 |
Correct |
12 ms |
8184 KB |
ok, correct split |
62 |
Correct |
13 ms |
8184 KB |
ok, correct split |
63 |
Correct |
11 ms |
8032 KB |
ok, correct split |
64 |
Correct |
12 ms |
8184 KB |
ok, correct split |
65 |
Correct |
11 ms |
8184 KB |
ok, correct split |
66 |
Correct |
9 ms |
7800 KB |
ok, correct split |
67 |
Correct |
12 ms |
8184 KB |
ok, correct split |
68 |
Correct |
9 ms |
7928 KB |
ok, correct split |
69 |
Correct |
9 ms |
7772 KB |
ok, correct split |
70 |
Correct |
9 ms |
7800 KB |
ok, correct split |
71 |
Correct |
12 ms |
8056 KB |
ok, correct split |
72 |
Correct |
12 ms |
8056 KB |
ok, correct split |
73 |
Correct |
11 ms |
8056 KB |
ok, correct split |
74 |
Correct |
13 ms |
8184 KB |
ok, correct split |
75 |
Correct |
12 ms |
8156 KB |
ok, correct split |
76 |
Correct |
12 ms |
8184 KB |
ok, correct split |
77 |
Correct |
12 ms |
8188 KB |
ok, correct split |
78 |
Correct |
10 ms |
7928 KB |
ok, correct split |
79 |
Correct |
10 ms |
7928 KB |
ok, correct split |
80 |
Correct |
14 ms |
8184 KB |
ok, correct split |
81 |
Correct |
12 ms |
8184 KB |
ok, correct split |
82 |
Correct |
14 ms |
8184 KB |
ok, correct split |
83 |
Correct |
13 ms |
8184 KB |
ok, correct split |
84 |
Correct |
11 ms |
8188 KB |
ok, no valid answer |
85 |
Correct |
11 ms |
8056 KB |
ok, correct split |
86 |
Correct |
11 ms |
8184 KB |
ok, correct split |
87 |
Correct |
9 ms |
7800 KB |
ok, no valid answer |
88 |
Correct |
9 ms |
7800 KB |
ok, no valid answer |
89 |
Correct |
11 ms |
8056 KB |
ok, no valid answer |
90 |
Correct |
12 ms |
8184 KB |
ok, no valid answer |
91 |
Correct |
10 ms |
8056 KB |
ok, no valid answer |
92 |
Correct |
11 ms |
8184 KB |
ok, no valid answer |
93 |
Correct |
11 ms |
8184 KB |
ok, no valid answer |
94 |
Correct |
176 ms |
23348 KB |
ok, correct split |
95 |
Correct |
242 ms |
29044 KB |
ok, correct split |
96 |
Correct |
225 ms |
27092 KB |
ok, correct split |
97 |
Correct |
57 ms |
12800 KB |
ok, correct split |
98 |
Correct |
60 ms |
13048 KB |
ok, correct split |
99 |
Correct |
78 ms |
15160 KB |
ok, correct split |
100 |
Correct |
233 ms |
24540 KB |
ok, correct split |
101 |
Correct |
206 ms |
23396 KB |
ok, correct split |
102 |
Correct |
179 ms |
22896 KB |
ok, correct split |
103 |
Correct |
179 ms |
22992 KB |
ok, correct split |
104 |
Correct |
171 ms |
22864 KB |
ok, correct split |
105 |
Correct |
99 ms |
15604 KB |
ok, correct split |
106 |
Correct |
169 ms |
23184 KB |
ok, correct split |
107 |
Correct |
160 ms |
20336 KB |
ok, correct split |
108 |
Correct |
179 ms |
20284 KB |
ok, correct split |
109 |
Correct |
248 ms |
23880 KB |
ok, correct split |
110 |
Correct |
231 ms |
24664 KB |
ok, correct split |
111 |
Correct |
245 ms |
24816 KB |
ok, correct split |
112 |
Correct |
231 ms |
23668 KB |
ok, correct split |
113 |
Correct |
212 ms |
23540 KB |
ok, correct split |
114 |
Correct |
25 ms |
9848 KB |
ok, correct split |
115 |
Correct |
24 ms |
9464 KB |
ok, correct split |
116 |
Correct |
219 ms |
24744 KB |
ok, correct split |
117 |
Correct |
225 ms |
24612 KB |
ok, correct split |
118 |
Correct |
176 ms |
21744 KB |
ok, correct split |
119 |
Correct |
166 ms |
21616 KB |
ok, correct split |
120 |
Correct |
183 ms |
25712 KB |
ok, correct split |
121 |
Correct |
163 ms |
19700 KB |
ok, no valid answer |
122 |
Correct |
155 ms |
19752 KB |
ok, no valid answer |
123 |
Correct |
229 ms |
24084 KB |
ok, no valid answer |
124 |
Correct |
232 ms |
24052 KB |
ok, no valid answer |
125 |
Correct |
132 ms |
20956 KB |
ok, no valid answer |
126 |
Correct |
93 ms |
18576 KB |
ok, no valid answer |
127 |
Correct |
167 ms |
21928 KB |
ok, no valid answer |