Submission #298809

#	Time	Username	Problem	Language	Result	Execution time	Memory
298809		square1001	Split the Attractions (IOI19_split)	C++14	40 / 100	147 ms	12792 KiB

split

#include "split.h"
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;
vector<int> find_split(int N, int A, int B, int C, vector<int> ea, vector<int> eb) {
	int M = ea.size();
	vector<vector<int> > G(N);
	for(int i = 0; i < M; ++i) {
		G[ea[i]].push_back(eb[i]);
		G[eb[i]].push_back(ea[i]);
	}
	bool subtask1 = true;
	for(int i = 0; i < N; ++i) {
		if(G[i].size() >= 3) {
			subtask1 = false;
		}
	}
	if(subtask1) {
		// subtask 1 (7 points)
		int ini = 0;
		for(int i = 0; i < N; ++i) {
			if(G[i].size() == 1) {
				ini = i;
				break;
			}
		}
		vector<int> seq = { ini };
		for(int i = 0; i < N - 1; ++i) {
			for(int j : G[seq.back()]) {
				if(i == 0 || j != seq[i - 1]) {
					seq.push_back(j);
					break;
				}
			}
		}
		vector<int> ans(N, -1);
		for(int i = 0; i < N; ++i) {
			if(i < A) ans[seq[i]] = 1;
			else if(i < A + B) ans[seq[i]] = 2;
			else ans[seq[i]] = 3;
		}
		return ans;
	}
	if(A == 1) {
		// subtask 2 (11 points)
		vector<bool> vis(N, false);
		int cnt = 0;
		vector<int> ans(N, -1);
		function<void(int)> dfs = [&](int pos) {
			if(cnt < B) {
				++cnt;
				ans[pos] = 2;
			}
			vis[pos] = true;
			for(int i : G[pos]) {
				if(!vis[i]) {
					dfs(i);
				}
			}
		};
		dfs(0);
		*find(ans.begin(), ans.end(), -1) = 1;
		for(int i = 0; i < N; ++i) {
			if(ans[i] == -1) ans[i] = 3;
		}
		return ans;
	}
	if(M == N - 1) {
		// subtask 3 (22 points)
		vector<int> par(N), subtree(N, 1);
		function<void(int, int)> build_tree = [&](int pos, int pre) {
			par[pos] = pre;
			for(int i : G[pos]) {
				if(i != pre) {
					build_tree(i, pos);
					subtree[pos] += subtree[i];
				}
			}
		};
		build_tree(0, -1);
		int mn = min({A, B, C});
		int mx = max({A, B, C});
		int spl = -1;
		for(int i = 0; i < N; ++i) {
			if(mn <= subtree[i] && subtree[i] <= N - mn) {
				spl = i;
				break;
			}
		}
		if(spl == -1) {
			return vector<int>(N, 0);
		}
		int mincol = (A == mn ? 1 : (B == mn ? 2 : 3));
		int maxcol = (C == mx ? 3 : (B == mx ? 2 : 1));
		int midcol = 6 - mincol - maxcol;
		vector<int> ans(N, -1);
		int rem = 0;
		function<void(int, int, int)> coloring = [&](int pos, int pre, int col) {
			if(rem > 0) {
				ans[pos] = col;
				--rem;
			}
			for(int i : G[pos]) {
				if(i != pre) {
					coloring(i, pos, col);
				}
			}
		};
		rem = mn;
		if(subtree[spl] * 2 <= N) {
			coloring(spl, par[spl], mincol);
		}
		else {
			coloring(par[spl], spl, mincol);
		}
		rem = N - mn - mx;
		if(subtree[spl] * 2 <= N) {
			coloring(par[spl], spl, midcol);
		}
		else {
			coloring(spl, par[spl], midcol);
		}
		for(int i = 0; i < N; ++i) {
			if(ans[i] == -1) {
				ans[i] = maxcol;
			}
		}
		return ans;
	}
	return vector<int>();
}

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