Submission #285252

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
285252	2020-08-28T13:53:28 Z	cookiedoth	Split the Attractions (IOI19_split)	C++14	40 / 100	1108 ms	22388 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 : g[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	1 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	1 ms	384 KB	ok, correct split
5	Correct	1 ms	384 KB	ok, correct split
6	Correct	1 ms	384 KB	ok, correct split
7	Correct	1075 ms	21948 KB	ok, correct split
8	Correct	1025 ms	20376 KB	ok, correct split
9	Correct	1101 ms	19616 KB	ok, correct split
10	Correct	982 ms	22256 KB	ok, correct split
11	Correct	1010 ms	22388 KB	ok, correct split

Subtask #2

11.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	384 KB	ok, correct split
2	Correct	0 ms	384 KB	ok, correct split
3	Correct	1 ms	384 KB	ok, correct split
4	Correct	995 ms	20328 KB	ok, correct split
5	Correct	1002 ms	16364 KB	ok, correct split
6	Correct	984 ms	22380 KB	ok, correct split
7	Correct	1002 ms	20076 KB	ok, correct split
8	Correct	1064 ms	18920 KB	ok, correct split
9	Correct	977 ms	16236 KB	ok, correct split
10	Correct	951 ms	17252 KB	ok, correct split
11	Correct	933 ms	17380 KB	ok, correct split
12	Correct	952 ms	17404 KB	ok, correct split

Subtask #3

22.0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	384 KB	ok, correct split
2	Correct	1004 ms	16336 KB	ok, correct split
3	Correct	380 ms	6768 KB	ok, correct split
4	Correct	1 ms	384 KB	ok, correct split
5	Correct	1108 ms	18200 KB	ok, correct split
6	Correct	1102 ms	17920 KB	ok, correct split
7	Correct	991 ms	17900 KB	ok, correct split
8	Correct	1010 ms	18944 KB	ok, correct split
9	Correct	1020 ms	17656 KB	ok, correct split
10	Correct	30 ms	5616 KB	ok, no valid answer
11	Correct	48 ms	8176 KB	ok, no valid answer
12	Correct	112 ms	19180 KB	ok, no valid answer
13	Correct	124 ms	16492 KB	ok, no valid answer
14	Correct	86 ms	21476 KB	ok, no valid answer

Subtask #4

0 / 24.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	384 KB	ok, correct split
2	Correct	1 ms	384 KB	ok, no valid answer
3	Correct	1 ms	384 KB	ok, correct split
4	Correct	1 ms	384 KB	ok, correct split
5	Correct	1 ms	384 KB	ok, correct split
6	Correct	1 ms	384 KB	ok, correct split
7	Correct	1 ms	384 KB	ok, correct split
8	Correct	1 ms	384 KB	ok, correct split
9	Correct	20 ms	896 KB	ok, correct split
10	Correct	25 ms	896 KB	ok, correct split
11	Correct	2 ms	384 KB	ok, correct split
12	Correct	24 ms	888 KB	ok, correct split
13	Correct	1 ms	384 KB	ok, correct split
14	Correct	1 ms	384 KB	ok, correct split
15	Correct	2 ms	384 KB	ok, correct split
16	Correct	1 ms	384 KB	ok, correct split
17	Correct	1 ms	384 KB	ok, correct split
18	Correct	1 ms	384 KB	ok, correct split
19	Correct	6 ms	384 KB	ok, correct split
20	Correct	9 ms	512 KB	ok, correct split
21	Correct	24 ms	768 KB	ok, correct split
22	Correct	24 ms	768 KB	ok, correct split
23	Correct	25 ms	888 KB	ok, correct split
24	Correct	24 ms	768 KB	ok, correct split
25	Correct	24 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	1 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	1 ms	384 KB	ok, correct split
5	Correct	1 ms	384 KB	ok, correct split
6	Correct	1 ms	384 KB	ok, correct split
7	Correct	1075 ms	21948 KB	ok, correct split
8	Correct	1025 ms	20376 KB	ok, correct split
9	Correct	1101 ms	19616 KB	ok, correct split
10	Correct	982 ms	22256 KB	ok, correct split
11	Correct	1010 ms	22388 KB	ok, correct split
12	Correct	1 ms	384 KB	ok, correct split
13	Correct	0 ms	384 KB	ok, correct split
14	Correct	1 ms	384 KB	ok, correct split
15	Correct	995 ms	20328 KB	ok, correct split
16	Correct	1002 ms	16364 KB	ok, correct split
17	Correct	984 ms	22380 KB	ok, correct split
18	Correct	1002 ms	20076 KB	ok, correct split
19	Correct	1064 ms	18920 KB	ok, correct split
20	Correct	977 ms	16236 KB	ok, correct split
21	Correct	951 ms	17252 KB	ok, correct split
22	Correct	933 ms	17380 KB	ok, correct split
23	Correct	952 ms	17404 KB	ok, correct split
24	Correct	1 ms	384 KB	ok, correct split
25	Correct	1004 ms	16336 KB	ok, correct split
26	Correct	380 ms	6768 KB	ok, correct split
27	Correct	1 ms	384 KB	ok, correct split
28	Correct	1108 ms	18200 KB	ok, correct split
29	Correct	1102 ms	17920 KB	ok, correct split
30	Correct	991 ms	17900 KB	ok, correct split
31	Correct	1010 ms	18944 KB	ok, correct split
32	Correct	1020 ms	17656 KB	ok, correct split
33	Correct	30 ms	5616 KB	ok, no valid answer
34	Correct	48 ms	8176 KB	ok, no valid answer
35	Correct	112 ms	19180 KB	ok, no valid answer
36	Correct	124 ms	16492 KB	ok, no valid answer
37	Correct	86 ms	21476 KB	ok, no valid answer
38	Correct	1 ms	384 KB	ok, correct split
39	Correct	1 ms	384 KB	ok, no valid answer
40	Correct	1 ms	384 KB	ok, correct split
41	Correct	1 ms	384 KB	ok, correct split
42	Correct	1 ms	384 KB	ok, correct split
43	Correct	1 ms	384 KB	ok, correct split
44	Correct	1 ms	384 KB	ok, correct split
45	Correct	1 ms	384 KB	ok, correct split
46	Correct	20 ms	896 KB	ok, correct split
47	Correct	25 ms	896 KB	ok, correct split
48	Correct	2 ms	384 KB	ok, correct split
49	Correct	24 ms	888 KB	ok, correct split
50	Correct	1 ms	384 KB	ok, correct split
51	Correct	1 ms	384 KB	ok, correct split
52	Correct	2 ms	384 KB	ok, correct split
53	Correct	1 ms	384 KB	ok, correct split
54	Correct	1 ms	384 KB	ok, correct split
55	Correct	1 ms	384 KB	ok, correct split
56	Correct	6 ms	384 KB	ok, correct split
57	Correct	9 ms	512 KB	ok, correct split
58	Correct	24 ms	768 KB	ok, correct split
59	Correct	24 ms	768 KB	ok, correct split
60	Correct	25 ms	888 KB	ok, correct split
61	Correct	24 ms	768 KB	ok, correct split
62	Correct	24 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	-