#include "split.h"
#include <bits/stdc++.h>
#define all(s) s.begin(),s.end()
#define sz(s) int(s.size())
#define pb push_back
#define pb push_back
#define ff first
#define ss second
typedef long long ll;
//typedef pair<int,int> ii;
const ll MAX=1e6;
using namespace std;
vector<int> gfo[MAX];
vector<pair<ll,ll>> ord;
ll tam[MAX], m[MAX];
ll a, b, c, n;
bool xd=false;
void dfstams(ll u, ll f){
for(auto v:gfo[u]){
if(v!=f){
dfstams(v,u);
tam[u]+=tam[v];
}
}
tam[u]++;
return;
}
ll cont;
void dfs(ll u, ll f, ll marc){
if(cont==ord[marc].ff)return;
m[u]=ord[marc].ss;
cont++;
if(cont==ord[marc].ff)return;
for(auto v:gfo[u]){
if(v!=f){
dfs(v,u,marc);
}
}
return;
}
bool lock(ll u, ll v){//arista
ll q=n-tam[u];///v
ll p=tam[u];/// u
cont=0;
if(p>=ord[0].ff && q>=ord[1].ff){
dfs(u, v, 0);
cont=0;
dfs(v, u, 1);
xd=true;
return true;
}
return false;
}
void clean(){
ord.clear();
for(int i=0; i<n; i++){
gfo[i].clear();
tam[i]=0;
m[i]=0;
}
return;
}
vector<int> find_split(int N, int A, int B, int C, vector<int> u, vector<int> v) {
a=A;
b=B;
c=C;
n=N;
ord.pb({a,1});
ord.pb({b,2});
ord.pb({c,3});
sort(all(ord));
vector<int> res;
for(int i=0; i<sz(u); i++){
gfo[u[i]].pb(v[i]);
gfo[v[i]].pb(u[i]);
}
dfstams(0, 0);
for(ll i=0; i<n; i++){
for(ll v:gfo[i]){
if(lock(i,v))break;
}
if(xd)break;
}
for(int i=0; i<n; i++){
if(xd && m[i]==0){
m[i]=ord[2].ss;
}
}
for(int i=0; i<n; i++){
res.pb(m[i]);
}
clean();
return res;
}
/*
9 8
2 3 4
0 1
0 7
0 2
1 6
1 3
2 5
2 8
2 4
8 7
2 3 3
0 1
1 2
1 7
1 3
3 4
4 5
4 6
7 6
4 2 2
*/
Compilation message
plants.cpp:1:10: fatal error: split.h: No such file or directory
1 | #include "split.h"
| ^~~~~~~~~
compilation terminated.
