#include "split.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn=200000+10;
vector<int>adj[maxn];
int high[maxn],sz[maxn];
int n,a,b,c,m,f=0,res[maxn],vis[maxn],s,t,bal[maxn];
vector<pair<int,int>>allv;
void clear(){
for(int i=0;i<=n;i++){
vis[i]=0;
}
}
void dfs(int u,int par=-1){
vis[u]=1;
bal[u]=high[u];
sz[u]=1;
for(auto x:adj[u]){
if(x==par||vis[x]==0){
continue;
}
bal[u]=min(bal[u],bal[x]);
}
for(auto x:adj[u]){
if(vis[x]==0){
high[x]=high[u]+1;
dfs(x,u);
sz[u]+=sz[x];
bal[u]=min(bal[u],bal[x]);
if(bal[x]>=high[u]){
f=1;
if(sz[x]>=a&&n-sz[x]>=b){
s=x;
t=u;
}
if(sz[x]>=b&&(n-sz[x])>=a){
s=u;
t=x;
}
}
}
}
}
void dfssolve(int u,int nar,int w){
if(a==0){
return ;
}
a--;
res[u]=w;
vis[u]=1;
for(auto x:adj[u]){
if(x==nar||vis[x]){
continue;
}
dfssolve(x,nar,w);
}
}
vector<int>rasbor(){
f=0;
dfs(0);
if(f==0){
return {};
}
//cout<<s<<" "<<t<<endl;
if(f==1&&s==-1){
vector<int>ret;
ret.resize(n);
return ret;
}
clear();
dfssolve(s,t,1);
clear();
swap(a,b);
dfssolve(t,s,2);
vector<int>ret;
for(int i=0;i<n;i++){
if(res[i]>=1){
ret.push_back(res[i]);
}else{
ret.push_back(3);
}
}
return ret;
}
vector<int>doham(){
exit(23);
return {};
}
vector<int>solve(){
vector<int>ret=rasbor();
if(ret.size()==0){
ret=doham();
}
for(int i=0;i<n;i++){
if(ret[i]!=0)
ret[i]=allv[ret[i]-1].second;
}
return ret;
}
vector<int> find_split(int n_, int a_, int b_, int c_, vector<int> p, vector<int> q) {
n=n_;
s=t=-1;
allv.push_back(make_pair(a_,1));
allv.push_back(make_pair(b_,2));
allv.push_back(make_pair(c_,3));
sort(allv.begin(),allv.end());
a=allv[0].first;
b=allv[1].first;
c=allv[2].first;
m=(int)p.size();
for(int i=0;i<m;i++){
adj[p[i]].push_back(q[i]);
adj[q[i]].push_back(p[i]);
}
//solve();
return solve();
}
Compilation message
rect.cpp:1:10: fatal error: split.h: No such file or directory
1 | #include "split.h"
| ^~~~~~~~~
compilation terminated.
