Submission #737196

#	Time	Username	Problem	Language	Result	Execution time	Memory
737196		NeroZein	Split the Attractions (IOI19_split)	C++17	33 / 100	507 ms	1048576 KiB

split

#include "split.h"
#include <bits/stdc++.h>
using namespace std;

vector<int> find_split(int n, int a_, int b_, int c_, vector<int> pp, vector<int> q) {
	vector<int> res(n);
	vector<pair<int,int>> pts = {{a_, 1}, {b_, 2}, {c_, 3}};
	sort(pts.begin(), pts.end()); 
	int m = (int) pp.size();
	vector<vector<int>> g(n); 
	for (int i = 0; i < m; ++i) {
		g[pp[i]].push_back(q[i]);
		g[q[i]].push_back(pp[i]);
	}
	if (a_ == 1) {
		vector<pair<int,int>> ptss = {{b_, 2}, {c_, 3}};
		sort(ptss.begin(), ptss.end()); 
		vector<bool> vis(n); 
		auto [s, c] = ptss[0]; 
		function<void(int)> Dfs = [&](int v) {
			vis[v] = true; 
			--s;
			res[v] = c; 
			for (int u : g[v]) {
				if (!s) return; 
				if (!vis[u]) {
					Dfs(u); 
				}
			}
		};
		Dfs(0);
		for (int i = 0; i < n; ++i) {
			if (vis[i]) continue; 
			for (int u : g[i]) {
				if (vis[u]) {
					res[i] = 1; 
					for (int j = 0; j < n; ++j) {
						if (!res[j]) {
							res[j] = ptss[1].second; 
						}
					}
					return res; 
				}
			}
		}
		return res; 
	}
	vector<int> pr(n); 
	vector<int> sz(n); 
	function<void(int, int)> Dfs = [&](int v, int p) {
		sz[v] = 1;
		for (int u : g[v]) {
			if (u != p) {
				pr[u] = v;
				Dfs(u, v); 
				sz[v] += sz[u];
			}
		}
	}; 
	Dfs(0, 0); 
	int s; 
	function<void(int, int, int)> color = [&](int v, int p, int c) {
		res[v] = c;
		--s;
		for (int u : g[v]) {
			if (!s) return; 
			if (u == p) continue; 
			color(u, v, c);
		}
	};
	for (int i = 0; i < n; ++i) {
		if (sz[i] >= pts[0].first && n - sz[i] >= pts[1].first) {
			s = pts[0].first;
			color(i, pr[i], pts[0].second);
			s = pts[1].first;
			color(pr[i], i, pts[1].second); 
			for (int j = 0; j < n; ++j) {
				if (!res[j]) {
					res[j] = pts[2].second; 
				}
			}
			break; 
		}
		if (n - sz[i] >= pts[0].first && sz[i] >= pts[1].first) {
			s = pts[1].first;
			color(i, pr[i], pts[1].second);
			s = pts[0].first;
			color(pr[i], i, pts[0].second); 
			for (int j = 0; j < n; ++j) {
				if (!res[j]) {
					res[j] = pts[2].second; 
				}
			}
			break; 
		}
	}
	return res;
}

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