Submission #1243206

#	Time	Username	Problem	Language	Result	Execution time	Memory
1243206		rayan_bd	Split the Attractions (IOI19_split)	C++20	40 / 100	51 ms	15212 KiB

split

#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 + 100;

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;
	--done;
	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])){
		//	cout << p[i] << " " << q[i] << endl;
			adj[p[i]].pb(q[i]);
			adj[q[i]].pb(p[i]);
		}
	}

	calc_sz();
	int cent = get_cent();

	//cout << "centroid: " << cent << endl;

	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;
}

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