oj.uz

Submission #298885

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

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB ok, correct split
2 Correct 1 ms 384 KB ok, correct split
3 Correct 1 ms 256 KB ok, correct split
4 Correct 1 ms 256 KB ok, correct split
5 Correct 1 ms 288 KB ok, correct split
6 Correct 1 ms 256 KB ok, correct split
7 Correct 86 ms 8820 KB ok, correct split
8 Correct 89 ms 8820 KB ok, correct split
9 Correct 93 ms 8820 KB ok, correct split
10 Correct 88 ms 8820 KB ok, correct split
11 Correct 89 ms 8820 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 97 ms 9336 KB ok, correct split
3 Correct 29 ms 4096 KB ok, correct split
4 Correct 1 ms 256 KB ok, correct split
5 Correct 111 ms 12152 KB ok, correct split
6 Correct 115 ms 11928 KB ok, correct split
7 Correct 109 ms 11896 KB ok, correct split
8 Correct 112 ms 13308 KB ok, correct split
9 Correct 113 ms 11904 KB ok, correct split
10 Correct 23 ms 3328 KB ok, no valid answer
11 Correct 37 ms 4736 KB ok, no valid answer
12 Correct 74 ms 9332 KB ok, no valid answer
13 Correct 86 ms 9204 KB ok, no valid answer
14 Correct 63 ms 9584 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 1 ms 256 KB ok, no valid answer
3 Correct 1 ms 256 KB ok, correct split
4 Correct 1 ms 288 KB ok, correct split
5 Correct 1 ms 288 KB ok, correct split
6 Correct 1 ms 256 KB ok, correct split
7 Correct 1 ms 256 KB ok, correct split
8 Correct 1 ms 256 KB ok, correct split
9 Incorrect 3 ms 640 KB WA in grader: Invalid length of the result.
10 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 Correct 1 ms 384 KB ok, correct split
3 Correct 1 ms 256 KB ok, correct split
4 Correct 1 ms 256 KB ok, correct split
5 Correct 1 ms 288 KB ok, correct split
6 Correct 1 ms 256 KB ok, correct split
7 Correct 86 ms 8820 KB ok, correct split
8 Correct 89 ms 8820 KB ok, correct split
9 Correct 93 ms 8820 KB ok, correct split
10 Correct 88 ms 8820 KB ok, correct split
11 Correct 89 ms 8820 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 -