oj.uz

Submission #298892

# Submission time Handle Problem Language Result Execution time Memory
298892 2020-09-14T09:29:36 Z square1001 Split the Attractions (IOI19_split) C++14
22 / 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() >= 2) {
				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];
			for(int i = 0; i < N; ++i) {
				cout << cutvert[i] << ' ' << weight[i] << endl;
			}
			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
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB ok, correct split
2 Incorrect 1 ms 256 KB secret mismatch
3 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB ok, correct split
2 Incorrect 1 ms 256 KB secret mismatch
3 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 99 ms 8696 KB ok, correct split
3 Correct 29 ms 3712 KB ok, correct split
4 Correct 1 ms 384 KB ok, correct split
5 Correct 115 ms 11640 KB ok, correct split
6 Correct 112 ms 11384 KB ok, correct split
7 Correct 109 ms 11384 KB ok, correct split
8 Correct 113 ms 12792 KB ok, correct split
9 Correct 109 ms 11384 KB ok, correct split
10 Correct 23 ms 3072 KB ok, no valid answer
11 Correct 35 ms 4480 KB ok, no valid answer
12 Correct 73 ms 8948 KB ok, no valid answer
13 Correct 82 ms 8860 KB ok, no valid answer
14 Correct 67 ms 8992 KB ok, no valid answer

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB ok, correct split
2 Correct 0 ms 256 KB ok, no valid answer
3 Incorrect 1 ms 256 KB secret mismatch
4 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB ok, correct split
2 Incorrect 1 ms 256 KB secret mismatch
3 Halted 0 ms 0 KB -