#include "split.h"
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
using namespace std;
long long int cnt=0,x1[100005],y1[100005],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];
}
}
int dfs(int x)
{
int g=road[x];
tag[x]=1;
while(g!=-1)
{
int now=map[g][0];
if(tag[now]==0)
{
y1[cnt]=x;
x1[cnt]=now;
cnt++;
dfs(now);
}
g=map[g][1];
}
return 0;
}
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;
srand (time(NULL));
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 qw=0;
while(qw<n)
{
dfs(qw);
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;
}
for(int i=0;i<n;i++)sum[i]=0;
buildp(0,-1);
find(0,0);
if(can==1)
{
vector<int> res(n);
for(int i=0;i<n;i++)
{
res[i]=ans[i];
if(res[i]==0)res[i]=c[1];
}
return res;
}
qw++;
}
vector<int> res(n);
}
Compilation message
split.cpp: In function 'int color(int, int)':
split.cpp:35:1: warning: control reaches end of non-void function [-Wreturn-type]
}
^
split.cpp: In function 'int find(int, int)':
split.cpp:72:1: warning: control reaches end of non-void function [-Wreturn-type]
}
^
split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:162:1: warning: control reaches end of non-void function [-Wreturn-type]
}
^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
ok, correct split |
2 |
Correct |
2 ms |
380 KB |
ok, correct split |
3 |
Correct |
3 ms |
376 KB |
ok, correct split |
4 |
Correct |
2 ms |
376 KB |
ok, correct split |
5 |
Correct |
2 ms |
376 KB |
ok, correct split |
6 |
Correct |
2 ms |
376 KB |
ok, correct split |
7 |
Correct |
92 ms |
13816 KB |
ok, correct split |
8 |
Correct |
86 ms |
12224 KB |
ok, correct split |
9 |
Correct |
84 ms |
12636 KB |
ok, correct split |
10 |
Correct |
91 ms |
13296 KB |
ok, correct split |
11 |
Correct |
92 ms |
14072 KB |
ok, correct split |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
ok, correct split |
2 |
Correct |
2 ms |
376 KB |
ok, correct split |
3 |
Correct |
3 ms |
376 KB |
ok, correct split |
4 |
Correct |
97 ms |
13148 KB |
ok, correct split |
5 |
Correct |
76 ms |
10872 KB |
ok, correct split |
6 |
Correct |
68 ms |
13304 KB |
ok, correct split |
7 |
Correct |
87 ms |
12940 KB |
ok, correct split |
8 |
Incorrect |
103 ms |
15472 KB |
invalid split: #1=1, #2=6, #3=99993 |
9 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
ok, correct split |
2 |
Correct |
71 ms |
10872 KB |
ok, correct split |
3 |
Correct |
26 ms |
4516 KB |
ok, correct split |
4 |
Correct |
2 ms |
376 KB |
ok, correct split |
5 |
Correct |
122 ms |
11896 KB |
ok, correct split |
6 |
Correct |
87 ms |
11784 KB |
ok, correct split |
7 |
Correct |
99 ms |
11768 KB |
ok, correct split |
8 |
Correct |
81 ms |
12372 KB |
ok, correct split |
9 |
Correct |
95 ms |
11920 KB |
ok, correct split |
10 |
Execution timed out |
2052 ms |
3448 KB |
Time limit exceeded |
11 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
ok, correct split |
2 |
Incorrect |
2 ms |
376 KB |
WA in grader: Invalid length of the result. |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
ok, correct split |
2 |
Correct |
2 ms |
380 KB |
ok, correct split |
3 |
Correct |
3 ms |
376 KB |
ok, correct split |
4 |
Correct |
2 ms |
376 KB |
ok, correct split |
5 |
Correct |
2 ms |
376 KB |
ok, correct split |
6 |
Correct |
2 ms |
376 KB |
ok, correct split |
7 |
Correct |
92 ms |
13816 KB |
ok, correct split |
8 |
Correct |
86 ms |
12224 KB |
ok, correct split |
9 |
Correct |
84 ms |
12636 KB |
ok, correct split |
10 |
Correct |
91 ms |
13296 KB |
ok, correct split |
11 |
Correct |
92 ms |
14072 KB |
ok, correct split |
12 |
Correct |
2 ms |
376 KB |
ok, correct split |
13 |
Correct |
2 ms |
376 KB |
ok, correct split |
14 |
Correct |
3 ms |
376 KB |
ok, correct split |
15 |
Correct |
97 ms |
13148 KB |
ok, correct split |
16 |
Correct |
76 ms |
10872 KB |
ok, correct split |
17 |
Correct |
68 ms |
13304 KB |
ok, correct split |
18 |
Correct |
87 ms |
12940 KB |
ok, correct split |
19 |
Incorrect |
103 ms |
15472 KB |
invalid split: #1=1, #2=6, #3=99993 |
20 |
Halted |
0 ms |
0 KB |
- |