#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();
}
if(s.fd(mkp(sub[x],x))!=s.end())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))
{
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 frs(int x,int p)
{
if(!a[1].fr)return;
a[1].fr--;
rs[x-1]=a[1].sc;
viz[x]=1;
for(int i=0;i<g[x].size();i++)
{
int y=g[x][i];
if(fnd(y)!=p || viz[y])continue;
frs(y,p);
}
}
void col(int x)
{
if(!a[2].fr)return;
a[2].fr--;
rs[x-1]=a[2].sc;
viz[x]=1;
for(int i=0;i<g[x].size();i++)
{
int y=g[x][i];
if(viz[y])continue;
col(y);
}
}
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*2<n)
{
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));
dfs(x,nd,x);
}
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;
frs(x,x);
col(nd);
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 frs(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 'void col(int)':
split.cpp:99: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:128:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(j=0;j<g[i].size();j++)
~^~~~~~~~~~~~
split.cpp:142:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=0;i<g[nd].size();i++)
~^~~~~~~~~~~~~
split.cpp:154:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=0;i<dg[pa.sc].size();i++)
~^~~~~~~~~~~~~~~~~
split.cpp:157:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(j=0;j<g[x].size();j++)
~^~~~~~~~~~~~
| # |
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 |
Runtime error |
17 ms |
14840 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 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 |
Correct |
8 ms |
7420 KB |
ok, correct split |
| 4 |
Correct |
182 ms |
19696 KB |
ok, correct split |
| 5 |
Correct |
144 ms |
18388 KB |
ok, correct split |
| 6 |
Runtime error |
131 ms |
46320 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
7420 KB |
ok, correct split |
| 2 |
Correct |
138 ms |
18448 KB |
ok, correct split |
| 3 |
Correct |
50 ms |
11692 KB |
ok, correct split |
| 4 |
Correct |
8 ms |
7416 KB |
ok, correct split |
| 5 |
Correct |
161 ms |
20208 KB |
ok, correct split |
| 6 |
Correct |
166 ms |
20080 KB |
ok, correct split |
| 7 |
Correct |
177 ms |
20080 KB |
ok, correct split |
| 8 |
Correct |
212 ms |
20980 KB |
ok, correct split |
| 9 |
Correct |
147 ms |
20080 KB |
ok, correct split |
| 10 |
Correct |
45 ms |
11012 KB |
ok, no valid answer |
| 11 |
Correct |
66 ms |
12788 KB |
ok, no valid answer |
| 12 |
Correct |
166 ms |
22640 KB |
ok, no valid answer |
| 13 |
Correct |
148 ms |
18676 KB |
ok, no valid answer |
| 14 |
Correct |
184 ms |
25836 KB |
ok, no valid answer |
| # |
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 |
7 ms |
7416 KB |
ok, correct split |
| 4 |
Correct |
8 ms |
7416 KB |
ok, correct split |
| 5 |
Runtime error |
17 ms |
14840 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 6 |
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 |
Runtime error |
17 ms |
14840 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 4 |
Halted |
0 ms |
0 KB |
- |
