Submission #285255

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
285255	2020-08-28T13:55:48 Z	cookiedoth	Split the Attractions (IOI19_split)	C++14	40 / 100	198 ms	22000 KB

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.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	384 KB	ok, correct split
2	Correct	1 ms	384 KB	ok, correct split
3	Correct	1 ms	384 KB	ok, correct split
4	Correct	0 ms	384 KB	ok, correct split
5	Correct	1 ms	384 KB	ok, correct split
6	Correct	0 ms	384 KB	ok, correct split
7	Correct	156 ms	21484 KB	ok, correct split
8	Correct	130 ms	19692 KB	ok, correct split
9	Correct	138 ms	19308 KB	ok, correct split
10	Correct	138 ms	21868 KB	ok, correct split
11	Correct	142 ms	21868 KB	ok, correct split

Subtask #2

11.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	384 KB	ok, correct split
2	Correct	0 ms	384 KB	ok, correct split
3	Correct	1 ms	288 KB	ok, correct split
4	Correct	158 ms	19948 KB	ok, correct split
5	Correct	151 ms	15888 KB	ok, correct split
6	Correct	144 ms	22000 KB	ok, correct split
7	Correct	146 ms	19564 KB	ok, correct split
8	Correct	198 ms	18280 KB	ok, correct split
9	Correct	134 ms	15812 KB	ok, correct split
10	Correct	81 ms	16740 KB	ok, correct split
11	Correct	85 ms	16740 KB	ok, correct split
12	Correct	86 ms	16740 KB	ok, correct split

Subtask #3

22.0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	384 KB	ok, correct split
2	Correct	128 ms	15872 KB	ok, correct split
3	Correct	38 ms	6520 KB	ok, correct split
4	Correct	1 ms	384 KB	ok, correct split
5	Correct	133 ms	17644 KB	ok, correct split
6	Correct	130 ms	17516 KB	ok, correct split
7	Correct	131 ms	17388 KB	ok, correct split
8	Correct	137 ms	18412 KB	ok, correct split
9	Correct	137 ms	17132 KB	ok, correct split
10	Correct	30 ms	5496 KB	ok, no valid answer
11	Correct	47 ms	8304 KB	ok, no valid answer
12	Correct	108 ms	19212 KB	ok, no valid answer
13	Correct	120 ms	16364 KB	ok, no valid answer
14	Correct	88 ms	21476 KB	ok, no valid answer

Subtask #4

0 / 24.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	384 KB	ok, correct split
2	Correct	0 ms	384 KB	ok, no valid answer
3	Correct	1 ms	384 KB	ok, correct split
4	Correct	0 ms	384 KB	ok, correct split
5	Correct	1 ms	384 KB	ok, correct split
6	Correct	0 ms	384 KB	ok, correct split
7	Correct	1 ms	384 KB	ok, correct split
8	Correct	0 ms	384 KB	ok, correct split
9	Correct	3 ms	768 KB	ok, correct split
10	Correct	3 ms	768 KB	ok, correct split
11	Correct	1 ms	384 KB	ok, correct split
12	Correct	3 ms	768 KB	ok, correct split
13	Correct	0 ms	384 KB	ok, correct split
14	Correct	1 ms	384 KB	ok, correct split
15	Correct	0 ms	384 KB	ok, correct split
16	Correct	1 ms	384 KB	ok, correct split
17	Correct	0 ms	384 KB	ok, correct split
18	Correct	0 ms	384 KB	ok, correct split
19	Correct	1 ms	384 KB	ok, correct split
20	Correct	1 ms	512 KB	ok, correct split
21	Correct	2 ms	768 KB	ok, correct split
22	Correct	2 ms	768 KB	ok, correct split
23	Correct	4 ms	768 KB	ok, correct split
24	Correct	3 ms	768 KB	ok, correct split
25	Correct	3 ms	768 KB	ok, correct split
26	Incorrect	4 ms	1152 KB	jury found a solution, contestant did not
27	Halted	0 ms	0 KB	-

Subtask #5

0 / 36.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	384 KB	ok, correct split
2	Correct	1 ms	384 KB	ok, correct split
3	Correct	1 ms	384 KB	ok, correct split
4	Correct	0 ms	384 KB	ok, correct split
5	Correct	1 ms	384 KB	ok, correct split
6	Correct	0 ms	384 KB	ok, correct split
7	Correct	156 ms	21484 KB	ok, correct split
8	Correct	130 ms	19692 KB	ok, correct split
9	Correct	138 ms	19308 KB	ok, correct split
10	Correct	138 ms	21868 KB	ok, correct split
11	Correct	142 ms	21868 KB	ok, correct split
12	Correct	0 ms	384 KB	ok, correct split
13	Correct	0 ms	384 KB	ok, correct split
14	Correct	1 ms	288 KB	ok, correct split
15	Correct	158 ms	19948 KB	ok, correct split
16	Correct	151 ms	15888 KB	ok, correct split
17	Correct	144 ms	22000 KB	ok, correct split
18	Correct	146 ms	19564 KB	ok, correct split
19	Correct	198 ms	18280 KB	ok, correct split
20	Correct	134 ms	15812 KB	ok, correct split
21	Correct	81 ms	16740 KB	ok, correct split
22	Correct	85 ms	16740 KB	ok, correct split
23	Correct	86 ms	16740 KB	ok, correct split
24	Correct	0 ms	384 KB	ok, correct split
25	Correct	128 ms	15872 KB	ok, correct split
26	Correct	38 ms	6520 KB	ok, correct split
27	Correct	1 ms	384 KB	ok, correct split
28	Correct	133 ms	17644 KB	ok, correct split
29	Correct	130 ms	17516 KB	ok, correct split
30	Correct	131 ms	17388 KB	ok, correct split
31	Correct	137 ms	18412 KB	ok, correct split
32	Correct	137 ms	17132 KB	ok, correct split
33	Correct	30 ms	5496 KB	ok, no valid answer
34	Correct	47 ms	8304 KB	ok, no valid answer
35	Correct	108 ms	19212 KB	ok, no valid answer
36	Correct	120 ms	16364 KB	ok, no valid answer
37	Correct	88 ms	21476 KB	ok, no valid answer
38	Correct	0 ms	384 KB	ok, correct split
39	Correct	0 ms	384 KB	ok, no valid answer
40	Correct	1 ms	384 KB	ok, correct split
41	Correct	0 ms	384 KB	ok, correct split
42	Correct	1 ms	384 KB	ok, correct split
43	Correct	0 ms	384 KB	ok, correct split
44	Correct	1 ms	384 KB	ok, correct split
45	Correct	0 ms	384 KB	ok, correct split
46	Correct	3 ms	768 KB	ok, correct split
47	Correct	3 ms	768 KB	ok, correct split
48	Correct	1 ms	384 KB	ok, correct split
49	Correct	3 ms	768 KB	ok, correct split
50	Correct	0 ms	384 KB	ok, correct split
51	Correct	1 ms	384 KB	ok, correct split
52	Correct	0 ms	384 KB	ok, correct split
53	Correct	1 ms	384 KB	ok, correct split
54	Correct	0 ms	384 KB	ok, correct split
55	Correct	0 ms	384 KB	ok, correct split
56	Correct	1 ms	384 KB	ok, correct split
57	Correct	1 ms	512 KB	ok, correct split
58	Correct	2 ms	768 KB	ok, correct split
59	Correct	2 ms	768 KB	ok, correct split
60	Correct	4 ms	768 KB	ok, correct split
61	Correct	3 ms	768 KB	ok, correct split
62	Correct	3 ms	768 KB	ok, correct split
63	Incorrect	4 ms	1152 KB	jury found a solution, contestant did not
64	Halted	0 ms	0 KB	-