Submission #589453

#	Time	Username	Problem	Language	Result	Execution time	Memory
589453		farhan132	Split the Attractions (IOI19_split)	C++17	0 / 100	125 ms	20468 KiB

split

#include "split.h"
#include <bits/stdc++.h>
 
using namespace std;
 
typedef int ll;
typedef pair<ll , ll> ii;
 
#define ff first
#define ss second
#define pb push_back
#define in insert

const ll N = 2e5 + 5;

ll n;

struct DSU{
	ll par[N], sz[N];
	void start(){
		for(ll i = 0; i < N; i++){
			par[i] = i; sz[i] = 1;
		}
		return;
	}
	ll find(ll a){
		if(a == par[a]) return par[a];
		return par[a] = find(par[a]);
	}
	void merge(ll x, ll y){
		x = find(x); y = find(y);
		if(x == y) return;
		if(sz[x] > sz[y]) swap(x, y);
		sz[y] += sz[x];
		par[x] = y;
		return;
	}
};

vector < ll > v[N], g[N];
ll sub[N];
ll up,down;

void dfs(ll s, ll p){
	sub[s] = 1;
	for(auto u : v[s]){
		if(u - p){
			dfs(u, s);
			sub[s] += sub[u];
		}
	}
	return;
}
ll centroid(ll s, ll p){
	for(auto u : v[s]){
		if(u - p){
			if(sub[u] > n/2){
				return centroid(u, s);
			}
		}
	}
	return s;
}
vector < ll > res;

void color(ll s, ll p, ll &rem, ll col){
	if(rem == 0) return;
	res[s] = col; rem--;
	for(auto u : v[s]){
		if(u - p){
			color(u, s, rem, col);
		}
	}
	return;
}

vector<int> find_split(int _n, int a, int b, int c, vector<int> p, vector<int> q) {
	vector < ii > all;
	all.pb({a, 1});
	all.pb({b, 2});
	all.pb({c, 3});
	sort(all.begin(), all.end());
	down = all[0].ff; up = all[1].ff; n = _n;

	ll m = p.size();

	vector < ii > extra;

	DSU T; T.start();

	for(ll i = 0; i < m; i++){
		ll x = p[i], y = q[i];
		g[x].pb(y);
		g[y].pb(x);
		if(T.find(x) == T.find(y)){
			extra.pb({x, y});
			continue;
		}
		T.merge(x, y);
		v[x].pb(y);
		v[y].pb(x);
	}
	res.resize(n, 0);

	dfs(0, -1);
	ll cen = centroid(0, -1);
	dfs(cen, -1);
	ll f = -1;
	for(auto u : v[cen]){
		if(sub[u] >= down){
			f = u;
			break;
		}
	}
	if(f == -1) return res;
	res.resize(0);
	res.resize(n, all[2].ss);

	color(f, cen, down, all[0].ss);

	up--;
	res[c] = all[1].ss;
	for(auto u : v[cen]){
		if(u == f) continue;
		color(u, cen, up, all[1].ss);
	}

	return res;
}

• Subtask 1: 0 / 7
• Subtask 2: 0 / 11
• Subtask 3: 0 / 22
• Subtask 4: 0 / 24
• Subtask 5: 0 / 36