Submission #285255

#	Time	Username	Problem	Language	Result	Execution time	Memory
285255		cookiedoth	Split the Attractions (IOI19_split)	C++14	40 / 100	198 ms	22000 KiB

split

/*

Code for problem B by cookiedoth
Generated 28 Aug 2020 at 01.11 PM


СТРОИМ КОММУНИЗМ РАБОТЯГИ!
 
                                    ╦═╩═╦═╩═█
                          ████▄▄▄═╦═╩═╦═╩═╦═█
                  ████████████████▄▄╦═╩═╦═╩═█
█═╦═╩═╦▄████████████████▀▀▀▀█████████▄╦═╩═╦═█
█═╩═╦═████████████████████▄═╦▀█████████═╦═╩═█
█═╦═▄██████████▀╩═╦═╩▄██████▄═╦▀████████▄═╦═█
█═╩═█████████▀╩═╦═╩═█████████▄╩═╦████████═╩═█
█═╦█████████▄═╦═╩═╦═▀█████████╦═╩═████████╦═█
█═╩███████████▄▄██▄═╦═▀████████═╦═████████╩═█
█═██████████████████▄═╦═▀█████▀═╩═█████████═█
█═████████████████████▄═╦═▀███╩═╦═█████████═█
█═╦████████████▀╩▀██████▄═╦═▀═╦═╩█████████╦═█
█═╩█████████▀═╩═╦═╩▀▀███▀▀╩═╦═╩═██████████╩═█
█═╦═██████▀═╦═▄▄█▄▄═╩═╦═╩═╦═╩═╦═╩▀███████═╦═█
█═╩═▀████═╩═▄█████████▄▄▄▄████▄═╦═╩█████▀═╩═█
█═╦═╩═██████████████████████████▄═▄████═╩═╦═█
█═╩═╦═╩▀█████████████████████████████▀╩═╦═╩═█
█═╦═╩═╦═╩▀▀███████████████████████▀▀╩═╦═╩═╦═█
█═╩═╦═╩═╦═╩═▀▀▀███████████████▀▀▀═╩═╦═╩═╦═╩═█
█═╦═╩═╦═╩═╦═╩═╦═╩═▀▀▀▀▀▀▀▀▀═╩═╦═╩═╦═╩═╦═╩═╦═█
█═╩═╦═╩═╦═╩═╦═╩═╦═╩═╦═╩═╦═╩═╦═╩═╦═╩═╦═╩═╦═╩═█
█▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄█

=_=
¯\_(ツ)_/¯
o_O

*/

#include "split.h"
#include <iostream>
#include <fstream>
#include <vector>
#include <set>
#include <map>
#include <bitset>
#include <algorithm>
#include <iomanip>
#include <cmath>
#include <ctime>
#include <functional>
#include <unordered_set>
#include <unordered_map>
#include <string>
#include <queue>
#include <deque>
#include <stack>
#include <complex>
#include <cassert>
#include <random>
#include <cstring>
#include <numeric>
#include <random>
#define ll long long
#define ld long double
#define null NULL
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define debug(a) cerr << #a << " = " << a << endl
#define forn(i, n) for (int i = 0; i < n; ++i)
#define length(a) (int)a.size()

using namespace std;

template<class T> int chkmax(T &a, T b) {
	if (b > a) {
		a = b;
		return 1;
	}
	return 0;
}

template<class T> int chkmin(T &a, T b) {
	if (b < a) {
		a = b;
		return 1;
	}
	return 0;
}

template<class iterator> void output(iterator begin, iterator end, ostream& out = cerr) {
	while (begin != end) {
		out << (*begin) << " ";
		begin++;
	}
	out << endl;
}

template<class T> void output(T x, ostream& out = cerr) {
	output(x.begin(), x.end(), out);
}

void fast_io() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
}

const int mx = 1e5 + 228;
vector<vector<int> > g, g_tree;
vector<int> ans, used;
int n;
vector<pair<int, int> > colors;

void dfs(int v) {
	used[v] = 1;
	for (auto v1 : g[v]) {
		if (used[v1] == 0) {
			// cerr << "tree_edge " << v << " " << v1 << endl;
			g_tree[v].push_back(v1);
			g_tree[v1].push_back(v);
			dfs(v1);
		}
	}
}

void build_g_tree() {
	used.resize(n);
	g_tree.resize(n);
	dfs(0);
}

int c, sz[mx], subtree_id[mx], subtree_size[mx], subtree_cnt;

void sz_dfs(int v, int pv) {
	sz[v] = 1;
	for (auto v1 : g_tree[v]) {
		if (v1 != pv) {
			sz_dfs(v1, v);
			sz[v] += sz[v1];
		}
	}
}

int find_centroid(int v, int pv) {
	for (auto v1 : g_tree[v]) {
		if (v1 != pv && 2 * sz[v1] >= n) {
			return find_centroid(v1, v);
		}
	}
	return v;
}

void dfs_subtree(int v, int pv) {
	subtree_id[v] = subtree_cnt;
	subtree_size[subtree_cnt]++;
	for (auto v1 : g_tree[v]) {
		if (v1 != pv) {
			dfs_subtree(v1, v);
		}
	}
}

void build_centroid_subtrees() {
	sz_dfs(0, 0);
	c = find_centroid(0, 0);
	for (auto v : g_tree[c]) {
		dfs_subtree(v, c);
		subtree_cnt++;
	}
	subtree_id[c] = subtree_cnt;
	// cerr << "c = " << c << endl;
	// cerr << "subtree_id" << endl;
	// output(subtree_id, subtree_id + n);
	// output(subtree_size, subtree_size + subtree_cnt);
}

int a, b, realm[mx];

void build_cmp(int target, int clr, int &cmp_sz, int v) {
	cmp_sz--;
	ans[v] = clr;
	// cerr << "v = " << v << endl;
	for (auto v1 : g[v]) {
		// cerr << "v1 = " << v1 << endl;
		// cerr << (realm[subtree_id[v1]] == target) << endl;
		// cerr << cmp_sz << endl;
		// cerr << ans[v1] << endl;
		if (cmp_sz && ans[v1] == colors[2].second && realm[subtree_id[v1]] == target) {
			build_cmp(target, clr, cmp_sz, v1);
		}
	}
}

void build_cmp(int target, int clr, int cmp_sz) {
	// cerr << "ans" << endl;
	// output(all(ans));
	for (int i = 0; i < n; ++i) {
		if (realm[subtree_id[i]] == target) {
			// cerr << "buid_cmp " << target << " " << clr << " " << cmp_sz << " " << i << endl;
			build_cmp(target, clr, cmp_sz, i);
			return;
		}
	}
	assert(0);
}

vector<pair<int, int> > edges;
vector<set<int> > sg;

int estimate(int v) {
	int res = subtree_size[v];
	used[v] = 1;
	for (auto v1 : sg[v]) {
		if (used[v1] == 0) {
			res += estimate(v1);
		}
	}
	return 1;
}

int cool_dfs(int v, int &sum) {
	sum += subtree_size[v];
	realm[v] = 1;
	if (sum >= a) {
		return 1;
	}
	used[v] = 2;
	for (auto v1 : sg[v]) {
		if (used[v1] != 2) {
			if (cool_dfs(v1, sum)) {
				return 1;
			}
		}
	}
	return 0;
}

void build_cmp() {
	fill(all(ans), colors[2].second);
	build_cmp(1, colors[0].second, a);
	build_cmp(0, colors[1].second, b);
}

void build_ans() {
	a = colors[0].first, b = colors[1].first;
	// cerr << "a, b = " << a << " " << b << endl;
	for (int i = 0; i < subtree_cnt; ++i) {
		if (subtree_size[i] >= a) {
			// cerr << "i = " << i << endl;
			realm[i] = 1;
			build_cmp();
			return;
		}
	}
	sg.resize(subtree_cnt);
	for (auto pp : edges) {
		if (pp.first != c && pp.second != c && subtree_id[pp.first] != subtree_id[pp.second]) {
			sg[subtree_id[pp.first]].insert(subtree_id[pp.second]);
			sg[subtree_id[pp.second]].insert(subtree_id[pp.first]);
			// cerr << "sg_edge " << subtree_id[pp.first] << " " << subtree_id[pp.second] << endl;
		}
	}
	used.assign(subtree_cnt, 0);
	for (int i = 0; i < subtree_cnt; ++i) {
		if (used[i] == 0) {
			if (estimate(i) >= a) {
				int sum = 0;
				cool_dfs(i, sum);
				build_cmp();
				return;
			}
		}
	}
}

void solve() {
	build_g_tree();
	build_centroid_subtrees();
	build_ans();
}

vector<int> find_split(int _n, int a, int b, int c, vector<int> p, vector<int> q) {
	n = _n;
	colors.emplace_back(a, 1);
	colors.emplace_back(b, 2);
	colors.emplace_back(c, 3);
	sort(all(colors));
	g.resize(n);
	int m = p.size();
	for (int i = 0; i < m; ++i) {
		g[p[i]].push_back(q[i]);
		g[q[i]].push_back(p[i]);
		edges.emplace_back(p[i], q[i]);
	}
	ans.resize(n);
	g_tree.resize(n);
	solve();
	return ans;
}

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