oj.uz

Submission #298883

# Submission time Handle Problem Language Result Execution time Memory
298883 2020-09-14T09:11:19 Z square1001 Split the Attractions (IOI19_split) C++14
29 / 100
 115 ms 12792 KB 
#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;
					}
					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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB ok, correct split
2 Correct 1 ms 256 KB ok, correct split
3 Correct 1 ms 256 KB ok, correct split
4 Correct 1 ms 384 KB ok, correct split
5 Correct 1 ms 256 KB ok, correct split
6 Correct 3 ms 256 KB ok, correct split
7 Correct 92 ms 9076 KB ok, correct split
8 Correct 95 ms 9076 KB ok, correct split
9 Correct 88 ms 9076 KB ok, correct split
10 Correct 86 ms 9076 KB ok, correct split
11 Correct 94 ms 9056 KB ok, correct split

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB ok, correct split
2 Correct 1 ms 256 KB ok, correct split
3 Incorrect 1 ms 256 KB invalid split: #1=1, #2=1, #3=3
4 Halted 0 ms 0 KB -

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB ok, correct split
2 Correct 104 ms 8696 KB ok, correct split
3 Correct 29 ms 3744 KB ok, correct split
4 Correct 1 ms 288 KB ok, correct split
5 Correct 115 ms 11732 KB ok, correct split
6 Correct 109 ms 11384 KB ok, correct split
7 Correct 111 ms 11384 KB ok, correct split
8 Correct 110 ms 12792 KB ok, correct split
9 Correct 111 ms 11384 KB ok, correct split
10 Correct 22 ms 3072 KB ok, no valid answer
11 Correct 36 ms 4480 KB ok, no valid answer
12 Correct 74 ms 8820 KB ok, no valid answer
13 Correct 82 ms 8696 KB ok, no valid answer
14 Correct 70 ms 8944 KB ok, no valid answer

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 416 KB ok, correct split
2 Correct 1 ms 256 KB ok, no valid answer
3 Correct 1 ms 384 KB ok, correct split
4 Incorrect 1 ms 256 KB invalid split: #1=4, #2=1, #3=6
5 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB ok, correct split
2 Correct 1 ms 256 KB ok, correct split
3 Correct 1 ms 256 KB ok, correct split
4 Correct 1 ms 384 KB ok, correct split
5 Correct 1 ms 256 KB ok, correct split
6 Correct 3 ms 256 KB ok, correct split
7 Correct 92 ms 9076 KB ok, correct split
8 Correct 95 ms 9076 KB ok, correct split
9 Correct 88 ms 9076 KB ok, correct split
10 Correct 86 ms 9076 KB ok, correct split
11 Correct 94 ms 9056 KB ok, correct split
12 Correct 1 ms 256 KB ok, correct split
13 Correct 1 ms 256 KB ok, correct split
14 Incorrect 1 ms 256 KB invalid split: #1=1, #2=1, #3=3
15 Halted 0 ms 0 KB -