#include "split.h"
#include <iostream>
#include <stdio.h>
using namespace std;
long long int can=0,ans[100005],f[100005],s,e,stop,a[2],b[2],c[2],sum[100005],t[100005],n,m,road[100005],map[1000005][2],tag[100005];
int buildp(int x,int father)
{
tag[x]=1;
f[x]=father;
sum[x]=1;
int g=road[x];
while(g!=-1)
{
int now=map[g][0];
if(tag[now]==0)sum[x]+=buildp(now,x);
g=map[g][1];
}
return sum[x];
}
int color(int x,int col)
{
if(s==e)return 0;
s++;
ans[x]=col;
int g=road[x];
while(g!=-1)
{
if(s==e)return 0;
int now=map[g][0];
if(now!=f[x] && now!=stop)color(now,col);
g=map[g][1];
}
}
int find(int x,int father)
{
if(sum[x]>=a[0] && father>=b[0])
{
can=1;
stop=f[x];
s=0;
e=a[0];
color(x,a[1]);
stop=x;
s=0;
e=b[0];
color(0,b[1]);
return 0;
}
if(father>=a[0] && sum[x]>=b[0])
{
can=1;
stop=x;
s=0;
e=a[0];
color(0,a[1]);
stop=f[x];
s=0;
e=b[0];
color(x,b[1]);
return 0;
}
int g=road[x];
while(g!=-1)
{
int now=map[g][0];
if(now!=f[x])find(now,father+(sum[x]-sum[now]));
if(can==1)return 0;
g=map[g][1];
}
}
vector<int> find_split(int N, int A, int B, int C, vector<int> p, vector<int> q) {
a[0]=A;
a[1]=1;
b[0]=B;
b[1]=2;
c[0]=C;
c[1]=3;
if(b[0]<=a[0] && b[0]<=c[0])
{
swap(a[0],b[0]);
swap(a[1],b[1]);
}
if(c[0]<=b[0] && c[0]<=a[0])
{
swap(a[0],c[0]);
swap(a[1],c[1]);
}
if(c[0]<=b[0])
{
swap(b[0],c[0]);
swap(b[1],c[1]);
}
n=N;
m=q.size();
for(int i=0;i<=n;i++)road[i]=-1;
for(int i=0;i<m;i++)
{
map[i*2][0]=p[i];
map[i*2][1]=road[q[i]];
road[q[i]]=i*2;
map[i*2+1][0]=q[i];
map[i*2+1][1]=road[p[i]];
road[p[i]]=i*2+1;
}
int cnt=0;
int st=(rand())%n,en=0;
t[0]=st;
tag[st]=1;
while(st<=en)
{
int x=t[st];
int g=road[x];
while(g!=-1)
{
int now=map[g][0];
if(tag[now]==0)
{
en++;
p[cnt]=x;
q[cnt]=now;
cnt++;
t[en]=now;
tag[now]=1;
}
g=map[g][1];
}
st++;
}
for(int i=0;i<=n;i++)
{
road[i]=-1;
tag[i]=0;
}
for(int i=0;i<cnt;i++)
{
map[i*2][0]=p[i];
map[i*2][1]=road[q[i]];
road[q[i]]=i*2;
map[i*2+1][0]=q[i];
map[i*2+1][1]=road[p[i]];
road[p[i]]=i*2+1;
}
buildp(0,-1);
find(0,0);
vector<int> res(n);
if(can==0)return res;
for(int i=0;i<n;i++)
{
res[i]=ans[i];
if(res[i]==0)res[i]=c[1];
}
return res;
}
Compilation message
split.cpp: In function 'int color(int, int)':
split.cpp:33:1: warning: control reaches end of non-void function [-Wreturn-type]
}
^
split.cpp: In function 'int find(int, int)':
split.cpp:70:1: warning: control reaches end of non-void function [-Wreturn-type]
}
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
jury found a solution, contestant did not |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
jury found a solution, contestant did not |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
jury found a solution, contestant did not |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
jury found a solution, contestant did not |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
jury found a solution, contestant did not |
| 2 |
Halted |
0 ms |
0 KB |
- |
