#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define all(x) x.begin(), x.end()
const int mxN = 1e5 + 5;
vector<int> adj[mxN];
int par[mxN], sz[mxN], ans[mxN], nby2;
int find(int u){
if(par[u] == u) return u;
return par[u] = find(par[u]);
}
bool unite(int u, int v){
u = find(u), v = find(v);
if(u == v) return 0;
par[u] = v;
return 1;
}
void calc_sz(int u = 0, int par = -1){
sz[u] = 1;
for(auto it : adj[u]){
if(it ^ par){
calc_sz(it, u);
sz[u] += sz[it];
}
}
}
int get_sz(int u, int par){
int ans = 1;
for(auto it : adj[u]){
if(it ^ par) continue;
ans += get_sz(it, u);
}
return ans;
}
int get_cent(int u = 0, int par = -1){
int mx = -1;
for(auto it : adj[u]){
if(it ^ par){
if(mx == -1) mx = it;
else if(sz[mx] < sz[it]) mx = it;
}
}
if(sz[mx] >= nby2){
return get_cent(mx, u);
}
return u;
}
int done = 0;
void work(int u, int par, int cc, int lstc){
if(done <= 0) ans[u] = lstc;
else ans[u] = cc;
for(auto it : adj[u]){
if(it ^ par){
work(it, u, cc, lstc);
}
}
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
int m = (int) p.size();
memset(ans, -1, sizeof(ans));
vector<pair<int, int>> ord = {{a, 1}, {b, 2}, {c, 3}};
sort(all(ord));
nby2 = n / 2;
for(int i = 0; i < n; ++i) par[i] = i;
for(int i = 0; i < m; ++i){
if(unite(p[i], q[i])){
adj[p[i]].pb(q[i]);
adj[q[i]].pb(p[i]);
}
}
calc_sz();
int cent = get_cent();
for(auto it : adj[cent]){
if(get_sz(it, cent) >= ord[0].fi){
done = ord[0].fi;
work(it, cent, ord[0].se, ord[2].se);
done = ord[1].fi;
work(cent, it, ord[1].se, ord[2].se);
break;
}
}
for(int i = 0; i < n; ++i){
if(ans[i] == -1){
for(int j = 0; j < n; ++j) ans[j] = 0;
break;
}
}
vector<int> res;
for(int i = 0; i < n; ++i) res.pb(ans[i]);
return res;
}
/*int main(){
freopen("input.in", "r", stdin);
freopen("output.out", "w", stdout);
return 0;
}*/
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |