Submission #425146

#	Time	Username	Problem	Language	Result	Execution time	Memory
425146		amoo_safar	Split the Attractions (IOI19_split)	C++17	11 / 100	146 ms	33772 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){
	u = Find(u);
	v = Find(v);
	if(u == v) return ;
	D[u].pb(v);
	D[v].pb(u);
	par[u] = v;
	sz[v] += sz[u];
}

int SetD(int u, int cnt, int d){
	if(cnt == 0) return 0;
	assert(col[u] == 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){
	if(cnt == 0) return 0;
	assert(col[u] == 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);
	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]);
	
	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 < 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: 0 / 7
• Subtask 2: 11 / 11
• Subtask 3: 0 / 22
• Subtask 4: 0 / 24
• Subtask 5: 0 / 36