#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]);
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);
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:165:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (i=0; i<p.size(); i++) {
~^~~~~~~~~
split.cpp:179:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (i=0; i<CtdV.size(); i++) {
~^~~~~~~~~~~~
split.cpp:184:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (ans.size()!=N) assert(false);
~~~~~~~~~~^~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
9 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 |
193 ms |
29040 KB |
ok, correct split |
8 |
Correct |
181 ms |
26864 KB |
ok, correct split |
9 |
Correct |
167 ms |
26132 KB |
ok, correct split |
10 |
Correct |
242 ms |
29412 KB |
ok, correct split |
11 |
Correct |
192 ms |
29592 KB |
ok, correct split |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
9 ms |
7800 KB |
ok, correct split |
2 |
Correct |
9 ms |
7800 KB |
ok, correct split |
3 |
Correct |
10 ms |
7828 KB |
ok, correct split |
4 |
Correct |
226 ms |
25812 KB |
ok, correct split |
5 |
Correct |
156 ms |
20328 KB |
ok, correct split |
6 |
Correct |
188 ms |
29552 KB |
ok, correct split |
7 |
Correct |
187 ms |
26608 KB |
ok, correct split |
8 |
Correct |
228 ms |
23984 KB |
ok, correct split |
9 |
Correct |
181 ms |
21744 KB |
ok, correct split |
10 |
Correct |
103 ms |
19548 KB |
ok, correct split |
11 |
Correct |
104 ms |
19556 KB |
ok, correct split |
12 |
Correct |
107 ms |
20060 KB |
ok, correct split |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
9 ms |
7800 KB |
ok, correct split |
2 |
Correct |
162 ms |
20292 KB |
ok, correct split |
3 |
Correct |
59 ms |
12796 KB |
ok, correct split |
4 |
Correct |
9 ms |
7800 KB |
ok, correct split |
5 |
Correct |
174 ms |
24308 KB |
ok, correct split |
6 |
Correct |
180 ms |
23924 KB |
ok, correct split |
7 |
Correct |
173 ms |
23752 KB |
ok, correct split |
8 |
Correct |
166 ms |
25072 KB |
ok, correct split |
9 |
Correct |
163 ms |
23664 KB |
ok, correct split |
10 |
Correct |
50 ms |
11896 KB |
ok, no valid answer |
11 |
Correct |
73 ms |
13696 KB |
ok, no valid answer |
12 |
Correct |
124 ms |
19848 KB |
ok, no valid answer |
13 |
Correct |
167 ms |
19696 KB |
ok, no valid answer |
14 |
Correct |
97 ms |
19688 KB |
ok, no valid answer |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
9 ms |
7800 KB |
ok, correct split |
2 |
Correct |
8 ms |
7800 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 |
8184 KB |
ok, correct split |
10 |
Correct |
12 ms |
8184 KB |
ok, correct split |
11 |
Correct |
9 ms |
7804 KB |
ok, correct split |
12 |
Correct |
12 ms |
8184 KB |
ok, correct split |
13 |
Correct |
8 ms |
7800 KB |
ok, correct split |
14 |
Correct |
9 ms |
7800 KB |
ok, correct split |
15 |
Correct |
9 ms |
7800 KB |
ok, correct split |
16 |
Correct |
9 ms |
7800 KB |
ok, correct split |
17 |
Correct |
9 ms |
7804 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 |
7928 KB |
ok, correct split |
21 |
Correct |
11 ms |
8184 KB |
ok, correct split |
22 |
Correct |
11 ms |
8056 KB |
ok, correct split |
23 |
Correct |
11 ms |
8184 KB |
ok, correct split |
24 |
Correct |
11 ms |
8188 KB |
ok, correct split |
25 |
Correct |
11 ms |
8184 KB |
ok, correct split |
26 |
Incorrect |
11 ms |
8056 KB |
WA in grader: Invalid length of the result. |
27 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
9 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 |
193 ms |
29040 KB |
ok, correct split |
8 |
Correct |
181 ms |
26864 KB |
ok, correct split |
9 |
Correct |
167 ms |
26132 KB |
ok, correct split |
10 |
Correct |
242 ms |
29412 KB |
ok, correct split |
11 |
Correct |
192 ms |
29592 KB |
ok, correct split |
12 |
Correct |
9 ms |
7800 KB |
ok, correct split |
13 |
Correct |
9 ms |
7800 KB |
ok, correct split |
14 |
Correct |
10 ms |
7828 KB |
ok, correct split |
15 |
Correct |
226 ms |
25812 KB |
ok, correct split |
16 |
Correct |
156 ms |
20328 KB |
ok, correct split |
17 |
Correct |
188 ms |
29552 KB |
ok, correct split |
18 |
Correct |
187 ms |
26608 KB |
ok, correct split |
19 |
Correct |
228 ms |
23984 KB |
ok, correct split |
20 |
Correct |
181 ms |
21744 KB |
ok, correct split |
21 |
Correct |
103 ms |
19548 KB |
ok, correct split |
22 |
Correct |
104 ms |
19556 KB |
ok, correct split |
23 |
Correct |
107 ms |
20060 KB |
ok, correct split |
24 |
Correct |
9 ms |
7800 KB |
ok, correct split |
25 |
Correct |
162 ms |
20292 KB |
ok, correct split |
26 |
Correct |
59 ms |
12796 KB |
ok, correct split |
27 |
Correct |
9 ms |
7800 KB |
ok, correct split |
28 |
Correct |
174 ms |
24308 KB |
ok, correct split |
29 |
Correct |
180 ms |
23924 KB |
ok, correct split |
30 |
Correct |
173 ms |
23752 KB |
ok, correct split |
31 |
Correct |
166 ms |
25072 KB |
ok, correct split |
32 |
Correct |
163 ms |
23664 KB |
ok, correct split |
33 |
Correct |
50 ms |
11896 KB |
ok, no valid answer |
34 |
Correct |
73 ms |
13696 KB |
ok, no valid answer |
35 |
Correct |
124 ms |
19848 KB |
ok, no valid answer |
36 |
Correct |
167 ms |
19696 KB |
ok, no valid answer |
37 |
Correct |
97 ms |
19688 KB |
ok, no valid answer |
38 |
Correct |
9 ms |
7800 KB |
ok, correct split |
39 |
Correct |
8 ms |
7800 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 |
8184 KB |
ok, correct split |
47 |
Correct |
12 ms |
8184 KB |
ok, correct split |
48 |
Correct |
9 ms |
7804 KB |
ok, correct split |
49 |
Correct |
12 ms |
8184 KB |
ok, correct split |
50 |
Correct |
8 ms |
7800 KB |
ok, correct split |
51 |
Correct |
9 ms |
7800 KB |
ok, correct split |
52 |
Correct |
9 ms |
7800 KB |
ok, correct split |
53 |
Correct |
9 ms |
7800 KB |
ok, correct split |
54 |
Correct |
9 ms |
7804 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 |
7928 KB |
ok, correct split |
58 |
Correct |
11 ms |
8184 KB |
ok, correct split |
59 |
Correct |
11 ms |
8056 KB |
ok, correct split |
60 |
Correct |
11 ms |
8184 KB |
ok, correct split |
61 |
Correct |
11 ms |
8188 KB |
ok, correct split |
62 |
Correct |
11 ms |
8184 KB |
ok, correct split |
63 |
Incorrect |
11 ms |
8056 KB |
WA in grader: Invalid length of the result. |
64 |
Halted |
0 ms |
0 KB |
- |