oj.uz

Submission #317577

# Submission time Handle Problem Language Result Execution time Memory
317577 2020-10-30T02:46:26 Z Kevin_Zhang_TW Balanced Tree (info1cup18_balancedtree) C++17
23 / 100
 4000 ms 41600 KB 
#include<bits/stdc++.h>
#define pb emplace_back
#define AI(i) begin(i), end(i)
using namespace std;
using ll = long long;
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] : ", args)
void kout() { cerr << endl; }
template<class T, class ...U>
void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
void debug(auto L, auto R) { while (L != R) cerr << *L << " \n"[next(L) == R], ++L; }
#else
#define debug(...) 0
#define DE(...) 0
#endif
const int MAX_N = 500010, inf = 1e9;
int n, c[MAX_N];
vector<int> edge[MAX_N];
void clear() {
	for (int i = 1; edge[i].size() ; ++i)
		edge[i].clear();
}
int dis[MAX_N], sz[MAX_N];
bool ban[MAX_N];
int dfs_sz(int x, int lst = -1) {
	sz[x] = 1;
	for (int u : edge[x]) if (u != lst && !ban[u])
		sz[x] += dfs_sz(u, x);
	return sz[x];
}
int dfs_cen(int x, int allsz, int lst = -1) {
	for (int u : edge[x]) if (u != lst && !ban[u])
		if (sz[u] * 2 > allsz)
			return dfs_cen(u, allsz, x);
	return x;
}

void chmin(int &v, int val) { v = min(v, val); }
int min_dep[2];
void dfs_update(int x, int lst = -1) {
	static int d;
	if (ban[x]) return;
	++d;
	chmin(dis[x], min_dep[c[x]] + d);
	chmin(min_dep[c[x]], d);
	for (int u : edge[x]) if (u != lst)
		dfs_update(u, x);
	--d;
}
void dfs_solve(int side) {
	if (ban[side]) return;
	int cen = dfs_cen(side, dfs_sz(side));

	min_dep[0] = min_dep[1] = inf;
	
	min_dep[ c[cen] ] = 0;

	ban[cen] = true;

	for (int u : edge[cen]) 
		dfs_update(u);

	min_dep[0] = min_dep[1] = inf;

	reverse(AI(edge[cen]));

	for (int u : edge[cen])
		dfs_update(u);

	chmin(dis[cen], min_dep[c[cen]]);

	for (int u : edge[cen])
		dfs_solve(u);
}
	
void cal_init() {
	for (int i = 1;i <= n;++i) {
		dis[i] = inf;
		ban[i] = false;
	}
}
int cal() {
	cal_init();
	dfs_solve(1);
	return *max_element(dis+1, dis+n+1);
}
int bfs(int s) {
	queue<pair<int,int>> q;
	vector<bool> vis(n+1);
	q.emplace(s, 0);
	vis[s] = true;
	while (q.size()) {
		auto [x, len] = q.front(); q.pop();
		if (x != s && c[x] == c[s])
			return len;
		for (int u : edge[x]) if (!vis[u])
			q.emplace(u, len+1), vis[u] = true;
	}
	return inf;
}
int brute_cal() {
	cal_init();
	int res = 0;
	for (int i = 1;i <= n;++i) 
		res = max(res, bfs(i));
	return res;
}
void brute_solve() {
	int res = inf, p;
	for (int s = 0;s < 1<<n;++s) {
		bool ok = true;
		for (int i = 0;i < n;++i)
			if (c[i+1] != -1 && c[i+1] != (s>>i&1)) 
				ok = false;
		if (!ok) continue;
		DE(s);
		vector<int> oldc(c, c+n+1);
		for (int i = 0;i < n;++i)
			c[i+1] = s>>i&1;
		int val = brute_cal();
		chmin(res, val);
		if (res == val) p = s;
		copy(AI(oldc), c);
		
	}
	if (res > n) {
		assert(false);
		return cout << -1 << '\n', void();
	}

	cout << res << '\n';
	for (int i = 0;i < n;++i)
		cout << (p>>i&1) << " \n"[i+1==n];
}
random_device rd;
mt19937 gen(rd());
int ra(int l, int r) {
	return uniform_int_distribution<int> (l, r)(gen);
}
pair<int, vector<int>> holan() {
	vector<int> oldc(c, c+n+1);
	for (int i = 1;i <= n;++i)
		if (c[i] == -1) c[i] = ra(0, 1);
	pair<int, vector<int>> res = {cal(), vector<int>(c, c+n+1)};
	copy(AI(oldc), c);
	return res;
}
void solve() {
	cin >> n;
	clear();
	for (int a, b, i = 1;i < n;++i) {
		cin >> a >> b;
		edge[a].pb(b);
		edge[b].pb(a);
	}

	for (int i = 1;i <= n;++i)
		cin >> c[i];

	int cn = count(c+1, c+n+1, -1), c0 = count(c+1, c+n+1, 0), c1 = count(c+1, c+n+1, 1);
	if ((c0==1) + (c1==1) > cn)
		return cout << -1 << '\n', void();

	if (!c0) {
		for (int i = 1;i <= n;++i)
			c[i] = 1;
		cn = 0;
	}
	if (!c1) {
		for (int i = 1;i <= n;++i)
			c[i] = 0;
		cn = 0;
	}

	if (n <= 17)
		return brute_solve(), void();

	if (cn == 0) {
		int val = cal();
		assert(val <= n);
//		if (val > n)
//			return cout << -1 << '\n', void();
		cout << val << '\n';
		for (int i = 1;i <= n;++i)
			cout << c[i] << " \n"[i==n];
	}
	else {
		pair<int, vector<int>> ans = {inf, {}};
		for (int x = 0;x < 50;++x)
			ans = min(ans, holan());

		auto [val, c] = ans;
		if (val > n)
			return cout << -1 << '\n', void();
		cout << val << '\n';
		for (int i = 1;i <= n;++i)
			cout << c[i] << " \n"[i==n];
	}
}

int32_t main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	int T;
	cin >> T;
	while (T--)
		solve();
}

Compilation message

balancedtree.cpp: In function 'void brute_solve()':
balancedtree.cpp:14:17: warning: statement has no effect [-Wunused-value]
   14 | #define DE(...) 0
      |                 ^
balancedtree.cpp:116:3: note: in expansion of macro 'DE'
  116 |   DE(s);
      |   ^~
balancedtree.cpp:133:13: warning: 'p' may be used uninitialized in this function [-Wmaybe-uninitialized]
  133 |   cout << (p>>i&1) << " \n"[i+1==n];
      |            ~^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 221 ms 12160 KB Output is correct
2 Correct 947 ms 12284 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 12792 KB Output is correct
2 Correct 178 ms 15200 KB Output is correct
3 Correct 120 ms 13304 KB Output is correct

Subtask #3
0.0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 1734 ms 13072 KB Output isn't correct
2 Execution timed out 4064 ms 22884 KB Time limit exceeded
3 Incorrect 3326 ms 16880 KB Output isn't correct

Subtask #4
0.0 / 45.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4072 ms 14440 KB Time limit exceeded
2 Incorrect 2050 ms 13292 KB Output isn't correct
3 Incorrect 2356 ms 13288 KB Output isn't correct
4 Incorrect 800 ms 12792 KB Output isn't correct
5 Incorrect 1305 ms 12996 KB Output isn't correct
6 Incorrect 2926 ms 13444 KB Output isn't correct
7 Correct 2013 ms 13108 KB Output is partially correct
8 Incorrect 778 ms 12664 KB Output isn't correct
9 Correct 1287 ms 12908 KB Output is partially correct

Subtask #5
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 221 ms 12160 KB Output is correct
2 Correct 947 ms 12284 KB Output is correct
3 Correct 62 ms 12792 KB Output is correct
4 Correct 178 ms 15200 KB Output is correct
5 Correct 120 ms 13304 KB Output is correct
6 Incorrect 1734 ms 13072 KB Output isn't correct
7 Execution timed out 4064 ms 22884 KB Time limit exceeded
8 Incorrect 3326 ms 16880 KB Output isn't correct
9 Execution timed out 4072 ms 14440 KB Time limit exceeded
10 Incorrect 2050 ms 13292 KB Output isn't correct
11 Incorrect 2356 ms 13288 KB Output isn't correct
12 Incorrect 800 ms 12792 KB Output isn't correct
13 Incorrect 1305 ms 12996 KB Output isn't correct
14 Incorrect 2926 ms 13444 KB Output isn't correct
15 Correct 2013 ms 13108 KB Output is partially correct
16 Incorrect 778 ms 12664 KB Output isn't correct
17 Correct 1287 ms 12908 KB Output is partially correct
18 Execution timed out 4070 ms 13836 KB Time limit exceeded
19 Execution timed out 4050 ms 19124 KB Time limit exceeded
20 Incorrect 3909 ms 14144 KB Output isn't correct
21 Execution timed out 4070 ms 41600 KB Time limit exceeded
22 Execution timed out 4013 ms 35752 KB Time limit exceeded