#include <algorithm>
#include <iostream>
#include <cassert>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <numeric>
#include <cstdio>
#include <string>
#include <vector>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <map>
#include <set>
using namespace std;
#define N 500005
#define ll long long int
#define fo(i,x,y) for(int i=x;i<=y;i++)
#define fs(ar,n) fo(i,1,n) cin>>ar[i]
#define sp " "
#define fast cin.tie(0);cout.tie(0);ios_base::sync_with_stdio(false)
#define pb push_back
#define ppb pop_back
#define fi first
#define se second
#define ii pair<int,int>
#define lli pair<ll,ll>
#define fast2 freopen ("in.txt","r",stdin);freopen ("out.txt","w",stdout);
#define inf 1000000000
#define MP make_pair
using namespace std;
#include "split.h"
using namespace std;
lli pp[N];
ll nn,mm,x,y,z,flag,mark[N],tut[N],tt[N];
vector<int> v[N],ans(nn);
ll f1(int ind,int back)
{
if(mark[ind])
return 0;
tt[ind]=back;
mark[ind]++;
ll top=1;
for(int i=0;i<v[ind].size();i++)
{
ll xx=v[ind][i];
if(mark[xx])
continue;
top+=f1(xx,ind);
}
return tut[ind]=top;
}
void f(int ind,int back)
{
// cerr<<ind<<endl;
if(mark[ind])
return;
mark[ind]++;
if(flag && !z)
return;
if(!flag && !y)
return;
if(!flag && y)
ans[ind]=2,y--;
if(flag && z)
ans[ind]=3,z--;
for(int i=0;i<v[ind].size();i++)
{
int xx=v[ind][i];
if(xx!=back)
f(xx,ind);
}
}
void f2(int ind,int back)
{
if(mark[ind] || !pp[2].fi)
return;
mark[ind]=1;
pp[2].fi--;
ans[ind]=pp[2].se;
for(int i=0;i<v[ind].size();i++)
{
ll xx=v[ind][i];
if(mark[xx] || back==xx)
continue;
f2(xx,ind);
}
}
void f3(int ind,int back)
{
if(mark[ind] || !pp[1].fi)
return;
mark[ind]=1;
pp[1].fi--;
ans[ind]=pp[1].se;
for(int i=0;i<v[ind].size();i++)
{
ll xx=v[ind][i];
if(mark[xx] || back==xx)
continue;
f3(xx,ind);
}
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
mm=p.size();
nn=n;
x=a;
y=b;
z=c;
int rt=0;
fo(i,0,mm-1)
{
int at=p[i];
int bt=q[i];
v[at].pb(bt);
v[bt].pb(at);
}
pp[1]=MP(a,1);
pp[2]=MP(b,2);
pp[3]=MP(c,3);
sort(pp+1,pp+4);
if(b>c)
flag=1;
// cerr<<ans.size()<<endl;
ans.resize(nn);
fo(i,0,nn-1)
if(v[i].size()<2)
rt=i;
f1(rt,rt);
memset(mark,0,sizeof(mark));
for(int i=0;i<n;i++)
{
// cout<<i<<sp<<tut[i]<<sp<<tt[i]<<endl;
if(tut[i]>pp[2].fi && n-tut[i]>pp[1].fi)
{
f2(i,tt[i]);
f3(tt[i],i);
for(int j=0;j<n;j++)
if(ans[j]==0)
{
int xxx=pp[3].se;
ans[j]=xxx;
}
// cerr<<" HELLO"<<sp<<i<<endl;
break;
}
}
return ans;
}
// int main() {
// int n, m, a, b, c;
// assert(5 == scanf("%d%d%d%d%d", &n, &m, &a, &b, &c));
// vector<int> p(m), q(m);
// for (int i=0; i<m; i++)
// assert(2 == scanf("%d%d", &p[i], &q[i]));
// fclose(stdin);
// vector<int> result = find_split(n, a, b, c, p, q);
// for (int i=0; i<(int)result.size(); i++)
// printf("%s%d", ((i>0)?" ":""), result[i]);
// printf("\n");
// fclose(stdout);
// return 0;
// }
Compilation message
split.cpp: In function 'long long int f1(int, int)':
split.cpp:50:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
50 | for(int i=0;i<v[ind].size();i++)
| ~^~~~~~~~~~~~~~
split.cpp: In function 'void f(int, int)':
split.cpp:77:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
77 | for(int i=0;i<v[ind].size();i++)
| ~^~~~~~~~~~~~~~
split.cpp: In function 'void f2(int, int)':
split.cpp:92:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
92 | for(int i=0;i<v[ind].size();i++)
| ~^~~~~~~~~~~~~~
split.cpp: In function 'void f3(int, int)':
split.cpp:107:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
107 | for(int i=0;i<v[ind].size();i++)
| ~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
16000 KB |
jury found a solution, contestant did not |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
16000 KB |
jury found a solution, contestant did not |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
16000 KB |
jury found a solution, contestant did not |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
16000 KB |
jury found a solution, contestant did not |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
16000 KB |
jury found a solution, contestant did not |
| 2 |
Halted |
0 ms |
0 KB |
- |
