#include "split.h"
#pragma GCC target("avx2")
#pragma GCC optimization("O3")
#pragma GCC optimization("unroll-loops")
#include<bits/stdc++.h>
#define rc(x) return cout<<x<<endl,0
#define pb push_back
#define mkp make_pair
#define in insert
#define er erase
#define fd find
#define fr first
#define sc second
typedef long long ll;
typedef long double ld;
const ll INF=0x3f3f3f3f3f3f3f3f;
const ll llinf=(1LL<<62);
const int inf=(1<<30);
const int nmax=1e5+50;
const int mod=1e9+7;
using namespace std;
int n,i,j,x,y,bl,nd,p[nmax],pr[nmax],sub[nmax],b[5],viz[nmax],mx,m;
vector<int>g[nmax],rs,dg[nmax],t[nmax];
pair<int,int>a[5],pa;
set<pair<int,int> >s;
void siz(int x,int p)
{
pr[x]=p;
sub[x]=1;
for(int i=0;i<t[x].size();i++)
{
int y=t[x][i];
if(y==p)continue;
siz(y,x);
sub[x]+=sub[y];
}
}
void dfs(int x,int pp,int c)
{
p[x]=c;
dg[c].pb(x);
for(int i=0;i<t[x].size();i++)
{
int y=t[x][i];
if(y==pp)continue;
dfs(y,x,c);
}
}
int fnd(int x)
{
if(p[x]==x)return x;
return p[x]=fnd(p[x]);
}
void uni(int x,int y)
{
x=fnd(x),y=fnd(y);
if(sub[x]<sub[y])swap(x,y);
while(!dg[y].empty())
{
p[dg[y].back()]=x;
dg[x].pb(dg[y].back());
dg[y].pop_back();
}
s.er(s.fd(mkp(sub[x],x)));
sub[x]+=sub[y];
s.in(mkp(sub[x],x));
}
void bas(int x,int y)
{
if(fnd(x)!=fnd(y))
{
//cout<<x<<" "<<y<<endl;
t[x].pb(y);
t[y].pb(x);
x=fnd(x),y=fnd(y);
if(sub[x]<sub[y])swap(x,y);
p[y]=x;
sub[x]+=sub[y];
}
}
void col(int x,int p)
{
if(!a[2].fr)return;
a[2].fr--;
rs[x-1]=a[2].sc;
for(int i=0;i<g[x].size();i++)
{
int y=g[x][i];
if(y==p || viz[y])continue;
col(y,x);
}
}
vector<int> find_split(int N,int A,int B,int C,vector<int>P,vector<int>Q)
{
n=N,b[1]=A,b[2]=B,b[3]=C,m=(int)P.size();
for(i=1;i<=3;i++)a[i]=mkp(b[i],i);
sort(a+1,a+4);
for(i=1;i<=n;i++)
{
p[i]=i;
sub[i]=1;
}
for(i=0;i<m;i++)
{
P[i]++,Q[i]++;
bas(P[i],Q[i]);
g[P[i]].pb(Q[i]);
g[Q[i]].pb(P[i]);
}
for(i=0;i<n;i++)rs.pb(0);
siz(1,0);
for(i=1;i<=n;i++)
{
mx=n-sub[i];
for(j=0;j<g[i].size();j++)
{
x=g[i][j];
if(x==pr[i])continue;
mx=max(mx,sub[x]);
}
if(mx<=n/2)
{
nd=i;
break;
}
}
siz(nd,0);
p[nd]=nd;
for(i=0;i<g[nd].size();i++)
{
x=g[nd][i];
s.in(mkp(sub[x],x));
//cout<<x<<" "<<sub[x]<<endl;
dfs(x,nd,x);
}
//cout<<nd<<endl;
while((int)s.size()>2)
{
if(s.rbegin()->fr>=a[1].fr)break;
pa=(*s.begin());
s.er(s.begin());
bl=0;
for(i=0;i<dg[pa.sc].size();i++)
{
x=dg[pa.sc][i];
for(j=0;j<g[x].size();j++)
{
y=g[x][j];
if(y==nd || fnd(y)==pa.sc)continue;
uni(x,y);
bl=1;
break;
}
if(bl)break;
}
}
x=s.rbegin()->sc;
if(sub[x]<a[1].fr)return rs;
for(i=0;i<dg[x].size();i++)
{
y=dg[x][i];
rs[y-1]=a[1].sc;
viz[y]=1;
}
col(nd,0);
for(i=0;i<n;i++)if(!rs[i])rs[i]=a[3].sc;
return rs;
}
Compilation message
split.cpp:3:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
#pragma GCC optimization("O3")
split.cpp:4:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
#pragma GCC optimization("unroll-loops")
split.cpp: In function 'void siz(int, int)':
split.cpp:30:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<t[x].size();i++)
~^~~~~~~~~~~~
split.cpp: In function 'void dfs(int, int, int)':
split.cpp:42:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<t[x].size();i++)
~^~~~~~~~~~~~
split.cpp: In function 'void col(int, int)':
split.cpp:86:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<g[x].size();i++)
~^~~~~~~~~~~~
split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:115:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(j=0;j<g[i].size();j++)
~^~~~~~~~~~~~
split.cpp:129:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=0;i<g[nd].size();i++)
~^~~~~~~~~~~~~
split.cpp:143:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=0;i<dg[pa.sc].size();i++)
~^~~~~~~~~~~~~~~~~
split.cpp:146:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(j=0;j<g[x].size();j++)
~^~~~~~~~~~~~
split.cpp:159:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=0;i<dg[x].size();i++)
~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
7388 KB |
ok, correct split |
| 2 |
Correct |
8 ms |
7288 KB |
ok, correct split |
| 3 |
Incorrect |
8 ms |
7416 KB |
invalid split: #1=2, #2=1, #3=1 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
7416 KB |
ok, correct split |
| 2 |
Correct |
8 ms |
7416 KB |
ok, correct split |
| 3 |
Incorrect |
8 ms |
7416 KB |
invalid split: #1=2, #2=2, #3=1 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
7416 KB |
invalid split: #1=2, #2=2, #3=1 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
7416 KB |
ok, correct split |
| 2 |
Correct |
8 ms |
7416 KB |
ok, no valid answer |
| 3 |
Correct |
8 ms |
7416 KB |
ok, correct split |
| 4 |
Incorrect |
8 ms |
7416 KB |
invalid split: #1=4, #2=5, #3=2 |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
7388 KB |
ok, correct split |
| 2 |
Correct |
8 ms |
7288 KB |
ok, correct split |
| 3 |
Incorrect |
8 ms |
7416 KB |
invalid split: #1=2, #2=1, #3=1 |
| 4 |
Halted |
0 ms |
0 KB |
- |
