Submission #298885

#	Time	Username	Problem	Language	Result	Execution time	Memory
298885		square1001	Split the Attractions (IOI19_split)	C++14	29 / 100	115 ms	13308 KiB

split

#include "split.h"
#include <vector>
#include <cassert>
#include <iostream>
#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(N <= 1000 && M <= 1000) {
		int mn = min({A, B, C});
		int mx = max({A, B, C});
		int mincol = (A == mn ? 1 : (B == mn ? 2 : 3));
		int maxcol = (C == mx ? 3 : (B == mx ? 2 : 1));
		int midcol = 6 - mincol - maxcol;
		vector<bool> black(N, true); // black = "separate to 3+ components"
		vector<int> cutvert(N, -1);
		vector<int> sepans(N, -1);
		vector<int> weight(N, 1);
		for(int i = 0; i < N; ++i) {
			vector<int> col(N, -1);
			int cnt = 0;
			function<void(int, int)> dfs = [&](int pos, int col_) {
				col[pos] = col_;
				++cnt;
				for(int j : G[pos]) {
					if(col[j] == -1 && j != i) {
						dfs(j, col_);
					}
				}
			};
			vector<int> compsize;
			for(int j = 0; j < N; ++j) {
				if(col[j] == -1 && j != i) {
					cnt = 0;
					dfs(j, compsize.size());
					compsize.push_back(cnt);
				}
			}
			if(compsize.size() >= 3) {
				black[i] = true;
				int mxptr = max_element(compsize.begin(), compsize.end()) - compsize.begin();
				if(compsize[mxptr] < mn) {
					return vector<int>(N, 0);
				}
				else if(mn <= compsize[mxptr] && compsize[mxptr] <= N - mn) {
					for(int j = 0; j < N; ++j) {
						sepans[j] = (col[j] == mxptr ? 1 : 0);
					}
					break;
				}
				else {
					for(int j = 0; j < N; ++j) {
						if(j != i && col[j] != mxptr) {
							cutvert[j] = i;
						}
					}
					weight[i] = N - compsize[mxptr];
				}
			}
		}
		if(sepans == vector<int>(N, -1)) {
			int initial = -1;
			for(int i = 0; i < N; ++i) {
				if(cutvert[i] != -1) {
					weight[i] = 0;
				}
				else {
					initial = i;
				}
			}
			sepans[initial] = 0;
			int sumweight = weight[initial];
			while(sumweight < mn) {
				bool found = false;
				for(int j = 0; j < N; ++j) {
					if(cutvert[j] != -1 || sepans[j] != -1) {
						continue;
					}
					bool valid = false;
					for(int k : G[j]) {
						if(sepans[k] != -1) {
							valid = true;
						}
					}
					if(!valid) continue;
					vector<bool> visncut(N, false);
					function<void(int)> dfsncut = [&](int pos) {
						visncut[pos] = true;
						for(int k : G[pos]) {
							if(cutvert[k] == -1 && k != j && sepans[k] == -1 && !visncut[k]) {
								dfsncut(k);
							}
						}
					};
					int comps = 0;
					for(int k = 0; k < N; ++k) {
						if(cutvert[k] == -1 && k != j && sepans[k] == -1 && !visncut[k]) {
							++comps;
							dfsncut(k);
						}
					}
					if(comps == 1) {
						sepans[j] = 0;
						sumweight += weight[j];
						found = true;
						break;
					}
				}
				assert(found);
			}
			for(int j = 0; j < N; ++j) {
				if(cutvert[j] == -1 && sepans[j] == -1) {
					sepans[j] = 1;
				}
			}
			for(int j = 0; j < N; ++j) {
				if(cutvert[j] != -1) {
					sepans[j] = sepans[cutvert[j]];
				}
			}
		}
		// suppose "sepans" is determined!
		int cntone = 0;
		for(int i = 0; i < N; ++i) {
			cntone += sepans[i];
		}
		if(cntone * 2 < N) {
			for(int i = 0; i < N; ++i) {
				sepans[i] ^= 1;
			}
		}
		int zero = -1, one = -1;
		for(int i = 0; i < N; ++i) {
			if(sepans[i] == 0 && zero == -1) {
				zero = i;
			}
			if(sepans[i] == 1 && one == -1) {
				one = i;
			}
		}
		int rem = 0;
		vector<int> ans(N, -1);
		function<void(int, int, int)> coloring = [&](int pos, int mode, int col) {
			if(rem != 0) {
				ans[pos] = col;
				--rem;
			}
			for(int i : G[pos]) {
				if(rem > 0 && ans[i] == -1 && sepans[i] == mode) {
					coloring(i, mode, col);
				}
			}
		};
		rem = mn;
		coloring(zero, 0, mincol);
		rem = N - mn - mx;
		coloring(one, 1, midcol);
		for(int i = 0; i < N; ++i) {
			if(ans[i] == -1) {
				ans[i] = maxcol;
			}
		}
		return ans;
	}
	else 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: 0 / 11
• Subtask 3: 22 / 22
• Subtask 4: 0 / 24
• Subtask 5: 0 / 36