Submission #425172

#	Time	Username	Problem	Language	Result	Execution time	Memory
425172		amoo_safar	Split the Attractions (IOI19_split)	C++17	100 / 100	334 ms	39232 KiB

split

	#include "split.h"

	#include <bits/stdc++.h>

	#define F first
	#define S second
	#define pb push_back
	#define all(x) x.begin(), x.end()
	#define debug(x) cerr << #x << " : " << x << '\n'

	using namespace std;

	typedef pair<int, int> pii;

	const int N = 2e5 + 10;

	vector<int> G[N], T[N], D[N];

	int col[N];

	int mk[N], sub[N];
	void Build(int u){
		mk[u] = 1;
		sub[u] = 1;
		for(auto adj : G[u]){
			if(mk[adj]) continue;
			T[u].pb(adj);
			T[adj].pb(u);
			Build(adj);
			sub[u] += sub[adj];
		}
	}

	int par[N], sz[N];
	int Find(int u){
		if(par[u] == u) return u;
		return par[u] = Find(par[u]);
	}
	void Unite(int u, int v){
		D[u].pb(v);
		D[v].pb(u);
		u = Find(u);
		v = Find(v);
		if(u == v) return ;
		par[u] = v;
		sz[v] += sz[u];
	}

	int SetD(int u, int cnt, int d){
		assert(col[u] == 0);
		if(cnt == 0) return 0;
		cnt --;
		col[u] = d;
		for(auto adj : D[u]){
			if(cnt == 0) return 0;
			if(col[adj] == 0)
				cnt = SetD(adj, cnt, d);
		}
		return cnt;
	}

	int SetG(int u, int cnt, int d){
		assert(col[u] == 0);
		if(cnt == 0) return 0;
		cnt --;
		col[u] = d;
		for(auto adj : G[u]){
			if(cnt == 0) return 0;
			if(col[adj] == 0)
				cnt = SetG(adj, cnt, d);
		}
		return cnt;
	}

	vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
		fill(sz, sz + N, 1);
		iota(par, par + N, 0);
		for(int i = 0; i < N; i++)
			G[i].clear(), T[i].clear(), D[i].clear();

		int m = p.size();
		for(int i = 0; i < m; i++)
			G[p[i]].pb(q[i]), G[q[i]].pb(p[i]);
		vector<int> ord = {1, 2, 3};

		if(a > b) swap(a, b), swap(ord[0], ord[1]);
		if(b > c) swap(b, c), swap(ord[2], ord[1]);
		if(a > b) swap(a, b), swap(ord[0], ord[1]);
		assert(a <= b);
		assert(b <= c);
		assert(a + b + c == n);

		memset(mk, 0, sizeof mk);
		Build(0);
		memset(mk, 0, sizeof mk);
		assert(sub[0] == n);

		bool fnd = false;
		int cen = 0;
		while(!fnd){
			fnd = true;
			for(auto adj : T[cen]){
				if(sub[adj] < sub[cen] && sub[adj] + sub[adj] > n){
					fnd = false;
					cen = adj;
					break;
				}
			}
		}

		fnd = false;
		
		for(int i = 0; i < n; i++){
			if((i != cen) && (!fnd)){
				// cerr << adj << "->" << i << '\n';
				if(sz[Find(i)] >= a){
					fnd = true;
					int rem = SetD(i, a, ord[0]);
					assert(rem == 0);
				}
			}
		}
		// for(int i = 0; i < m; i++){
		// 	if((p[i] != cen) && (q[i] != cen) && (!fnd)){
		// 		// cerr << "!! " << p[i] << ' ' << q[i] << '\n';
		// 		Unite(p[i], q[i]);
		// 		if(sz[Find(p[i])] >= a){
		// 			fnd = true;
		// 			int rem = SetD(p[i], a, ord[0]);
		// 			assert(rem == 0);
		// 		}
		// 	}
		// }
		for(int i = 0; i < n; i++){
			for(auto adj : T[i]){
				if((adj != cen) && (i != cen) && (!fnd)){
					// cerr << adj << "->" << i << '\n';
					Unite(adj, i);
					if(sz[Find(adj)] >= a){
						fnd = true;
						int rem = SetD(adj, a, ord[0]);
						assert(rem == 0);
					}
				}
			}
		}
		for(int i = 0; i < n; i++){
			for(auto adj : G[i]){
				if((adj != cen) && (i != cen) && (!fnd)){
					// cerr << adj << "->" << i << '\n';
					Unite(adj, i);
					if(sz[Find(adj)] >= a){
						fnd = true;
						int rem = SetD(adj, a, ord[0]);
						assert(rem == 0);
					}
				}
			}
		}
		// debug(cen);
		// for(int i = 0; i < n; i++)
		// 	cerr << sz[Find(i)] << ' ';
		// cerr << '\n';
		// cerr << "!! " << a << ' ' << b << ' ' << c << '\n';
		// cerr << ord[0] << ord[1] << ord[2] << '\n';
		if(!fnd)
			return vector<int>(n, 0);
		
		int rem = SetG(cen, b, ord[1]);
		assert(rem == 0);
		for(int i = 0; i < n; i++) if(col[i] == 0) col[i] = ord[2];
		vector<int> res;
		for(int i = 0; i < n; i++)
			res.pb(col[i]);
		return res;
	}

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