제출 #1049005

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1049005		Onur_Ilgaz	Split the Attractions (IOI19_split)	C++17	100 / 100	83 ms	25680 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) {
	int m = p.size();
	vector <vector<int> > graph(n), tree(n);
	vector <int> tin(n), tlow(n), sub(n);
	vector <int32_t> ans(n);
	vector <bool> vis(n);
	vector <pair<int, int> > duck = {{a, 1}, {b, 2}, {c, 3}};
	sort(duck.begin(), duck.end()); // sonuncusu çöp

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

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

	int time = 0, center = 0;
	auto dfs = [&](int node, int ata, auto&& dfs) -> void {
		tin[node] = time++;
		vis[node] = 1;
		tlow[node] = tin[node];
		sub[node] = 1;
		int mx = 0;
		for(auto it:graph[node]) {
			if(it == ata) continue;
			if(vis[it]) {
				tlow[node] = min(tlow[node], tlow[it]);
			}
			else {
				dfs(it, node, dfs);
				sub[node] += sub[it];
				tree[node].push_back(it);
				tree[it].push_back(node);
				tlow[node] = min(tlow[node], tlow[it]);
			}
			mx = max(sub[it], mx);
		}
		if(mx <= n / 2 and n - sub[node] <= n / 2) {
			center = node;
		}
	};
	dfs(0, 0, dfs);

	// cerr << center << "\n";
	set <int> noup;
	for(auto it:tree[center]) {
		if(tin[it] < tin[center]) {
			if(n - sub[center] >= duck[1].first) swap(duck[1], duck[0]);
			if(n - sub[center] >= duck[0].first) {
				size = duck[0].first;
				taguntil(it, center, duck[0].second, tree, taguntil);
				size = duck[1].first;
				taguntil(center, it, duck[1].second, tree, taguntil);
				for(auto &it:ans) if(!it) it = duck[2].second;
				return ans;
			}
		}
		else {
			noup.insert(it);
			if(sub[it] >= duck[1].first) swap(duck[1], duck[0]);
			if(sub[it] >= duck[0].first) {
				size = duck[0].first;
				taguntil(it, center, duck[0].second, tree, taguntil);
				size = duck[1].first;
				taguntil(center, it, duck[1].second, tree, taguntil);
				for(auto &it:ans) if(!it) it = duck[2].second;
				return ans;
			}
		}
	}

	// worst casede bile bütün subtreeler floor(n / 3)'ten küçük
	int topsize = n -  sub[center];
	for(auto it:tree[center]) {
		if(tin[it] < tin[center]) {
			continue;
		}
		if(tlow[it] < tin[center]) {
			topsize += sub[it];
			noup.erase(it);
		}
		if(topsize >= duck[1].first) swap(duck[1], duck[0]);
		if(topsize >= duck[0].first) {
			size = duck[1].first - 1;
			ans[center] = duck[1].second;
			for(auto child:noup) {
				if(size) taguntil(child, center, duck[1].second, tree, taguntil);
			}

			size = duck[0].first;
			taguntil(it, center, duck[0].second, graph, taguntil);
			for(auto &it:ans) if(!it) it = duck[2].second;
			return ans;
		}
	}
	return ans;
}

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