Submission #1047490

#	Time	Username	Problem	Language	Result	Execution time	Memory
1047490		Onur_Ilgaz	Split the Attractions (IOI19_split)	C++17	0 / 100	513 ms	1048580 KiB

split

#include "split.h"
#include <bits/stdc++.h>
#define int long long
#define inf ((int)1e18)
const int N = 100000;
using namespace std;

vector<int32_t> find_split(int32_t n, int32_t a, int32_t b, int32_t c, vector<int32_t> p, vector<int32_t> q) {
	vector <int32_t> sub(n), ans(n);
	vector <vector<int> > adj(n);
	int m = p.size();
	vector <pair<int, int> > fuck = {{a, 1}, {b, 2}, {c, 3}};

	for(int i = 0; i < m; i++) {
		int a = p[i], b = q[i];
		adj[a].push_back(b);
		adj[b].push_back(a);
	}

	int size = 0;
	auto taguntil = [&](int node, int ata, int tag, auto&& dfs) -> void {
		size--;
		ans[node] = tag;
		for(auto it:adj[node]) {
			if(it == ata) continue;
			if(size) dfs(it, node, tag, dfs);
		}
	};

	auto dfs = [&](int node, int ata, auto&& dfs) -> bool {
		// cout << node << " " << ata << endl;
		sub[node] = 1;
		for(auto it:adj[node]) {
			if(it == ata) continue;
			if(dfs(it, node, dfs)) {
				return true;
			}
			sub[node] += sub[it];
		}		
		if(sub[node] == fuck[0].first) {
			size = fuck[0].first;
			taguntil(node, ata, fuck[0].second, taguntil);
			size = fuck[1].first;
			taguntil(ata, node, fuck[1].second, taguntil);
			for(auto &it:ans) if(it == 0) it = fuck[2].second;
			return true;
		}
		if(n - sub[node] + 1 == fuck[0].first) {
			size = fuck[0].first - 1;
			taguntil(ata, node, fuck[0].second, taguntil);
			size = fuck[1].first + 1;
			taguntil(node, ata, fuck[1].second, taguntil);
			ans[node] = fuck[0].first;
			for(auto &it:ans) if(it == 0) it = fuck[2].second;
			return true;
		}
		return false;
	};

	if(dfs(0, 0, dfs)) return ans;
	swap(fuck[0], fuck[1]);
	if(dfs(0, 0, dfs)) return ans;
	swap(fuck[0], fuck[2]);
	if(dfs(0, 0, dfs)) return ans;
	return ans;
}

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