oj.uz

Submission #317154

# Submission time Handle Problem Language Result Execution time Memory
317154 2020-10-29T04:19:12 Z 8e7 Balanced Tree (info1cup18_balancedtree) C++14
0 / 100
 330 ms 31224 KB 
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#define ll long long
#define pii pair<int, int>
#define ff first
#define ss second
#define maxn 500005
using namespace std;
const int inf = 8e7;
vector<int> adj[maxn];
int c[maxn];
pii val[maxn];
pii dfs(int n, int par) {
	pii ret = make_pair(inf, inf);
	for (int v:adj[n]) {
		if (v != par) {
			pii res = dfs(v, n);
			ret.ff = min(ret.ff, res.ff + 1);
			ret.ss = min(ret.ss, res.ss + 1);
		}
	}
	val[n] = ret;
	if (c[n]) ret.ss = 0;
	else ret.ff = 0;
	return ret;
}
void dfs2(int n, int par, pii cur) {
	val[n].ff = min(val[n].ff, cur.ff);
	val[n].ss = min(val[n].ss, cur.ss);
	//cout << n << " " << cur.ff << " " << cur.ss << " " << val[n].ff << " " << val[n].ss<< endl;
	for (int v:adj[n]) {
		if (v != par) {
			pii upd = cur;
			for (int u:adj[n]) {
				if (u != par && u != v) {
					upd.ff = min(upd.ff, val[u].ff + 1);
					upd.ss = min(upd.ss, val[u].ss + 1);
					if (c[u]) upd.ss = 1;
					else upd.ff = 1;
				}
			}
			if (c[n]) {
				upd.ss = 0;
			} else {
				upd.ff = 0;
			}
			upd.ff++, upd.ss++;
			dfs2(v, n, upd);
		}
	}
}
int main() {
	ios_base::sync_with_stdio(0);cin.tie(0);
	int t;
	cin >> t;
	while (t--) {
		int n;
		cin >> n;
		for (int i = 1;i <= n;i++) c[i] = 0, adj[i].clear();
		for (int i = 0;i < n - 1;i++) {
			int a, b;
			cin >> a >> b;
			adj[a].push_back(b);
			adj[b].push_back(a);
		}
		int c0 = 0, c1 = 0;
		vector<int> pos;
		for (int i = 1;i <= n;i++) {
			cin >> c[i];
			if (c[i] == 1) c1++;
			else if (c[i] == 0) c0++;
			else pos.push_back(i);
		}
		int s = pos.size();
		int ans = inf, ind = 0;
		if (s) {
			if (n > 17) {
				return 0;
			}
			for (int i = 0;i < (1<<s);i++) {
				for (int j = 0;j < s;j++) {
					c[pos[j]] = (i & (1<<j)) ? (c1++, 1) : (c0++, 0);
				}
				dfs(1, 0);
				pii temp = make_pair(inf, inf);
				dfs2(1, 0, temp);
				int num = 0;
				for (int i = 1;i <= n;i++) {
					if (c[i]) num = max(num, val[i].ss);
					else num = max(num, val[i].ff);
				}
				if (num < ans) {
					ans = num, ind = i;
				}
			}
			for (int j = 0;j < s;j++) {
				c[pos[j]] = (ind & (1<<j)) ? 1 : 0;
			}
		} else {
			dfs(1, 0);
			pii temp = make_pair(inf, inf);
			dfs2(1, 0, temp);
			int num = 0;
			for (int i = 1;i <= n;i++) {
				if (c[i]) num = max(num, val[i].ss);
				else num = max(num, val[i].ff);
			}
			ans = num;
		}
		if (ans >= inf) {
			cout << -1 << endl;
		} else {
			cout << ans << endl;
			for (int i = 1;i <= n;i++) {
				//cout << val[i].ff << " " << val[i].ss << endl;
				cout << c[i] << " ";
			}
			cout << endl;
		}
	}
}
/*
3
3
1 2
2 3
0 0 -1
4
1 2
2 3
2 4
0 1 0 0
6
1 2
2 3
2 4
4 5
4 6
1 0 0 -1 1 0

1
8
1 2
1 3
3 4
3 5
3 6
5 7
5 8
0 1 0 0 0 0 0 1

1
6
1 2
2 3
2 4
4 5
4 6
1 0 0 -1 1 0
 */

Subtask #1
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 15 ms 12288 KB Output isn't correct
2 Incorrect 17 ms 12160 KB Output isn't correct

Subtask #2
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 48 ms 12792 KB Output isn't correct
2 Correct 74 ms 14972 KB Output is correct
3 Incorrect 52 ms 13304 KB Output isn't correct

Subtask #3
0.0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 12160 KB Unexpected end of file - int32 expected
2 Incorrect 53 ms 16120 KB Unexpected end of file - int32 expected
3 Incorrect 23 ms 13568 KB Unexpected end of file - int32 expected

Subtask #4
0.0 / 45.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 12800 KB Unexpected end of file - int32 expected
2 Incorrect 9 ms 12160 KB Unexpected end of file - int32 expected
3 Incorrect 9 ms 12192 KB Unexpected end of file - int32 expected
4 Incorrect 9 ms 12032 KB Unexpected end of file - int32 expected
5 Incorrect 9 ms 12160 KB Unexpected end of file - int32 expected
6 Incorrect 10 ms 12288 KB Unexpected end of file - int32 expected
7 Incorrect 9 ms 12160 KB Unexpected end of file - int32 expected
8 Incorrect 9 ms 12160 KB Unexpected end of file - int32 expected
9 Incorrect 9 ms 12288 KB Unexpected end of file - int32 expected

Subtask #5
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 15 ms 12288 KB Output isn't correct
2 Incorrect 17 ms 12160 KB Output isn't correct
3 Incorrect 48 ms 12792 KB Output isn't correct
4 Correct 74 ms 14972 KB Output is correct
5 Incorrect 52 ms 13304 KB Output isn't correct
6 Incorrect 9 ms 12160 KB Unexpected end of file - int32 expected
7 Incorrect 53 ms 16120 KB Unexpected end of file - int32 expected
8 Incorrect 23 ms 13568 KB Unexpected end of file - int32 expected
9 Incorrect 16 ms 12800 KB Unexpected end of file - int32 expected
10 Incorrect 9 ms 12160 KB Unexpected end of file - int32 expected
11 Incorrect 9 ms 12192 KB Unexpected end of file - int32 expected
12 Incorrect 9 ms 12032 KB Unexpected end of file - int32 expected
13 Incorrect 9 ms 12160 KB Unexpected end of file - int32 expected
14 Incorrect 10 ms 12288 KB Unexpected end of file - int32 expected
15 Incorrect 9 ms 12160 KB Unexpected end of file - int32 expected
16 Incorrect 9 ms 12160 KB Unexpected end of file - int32 expected
17 Incorrect 9 ms 12288 KB Unexpected end of file - int32 expected
18 Incorrect 12 ms 12544 KB Unexpected end of file - int32 expected
19 Incorrect 58 ms 16120 KB Unexpected end of file - int32 expected
20 Incorrect 9 ms 12032 KB Unexpected end of file - int32 expected
21 Incorrect 330 ms 31224 KB Unexpected end of file - int32 expected
22 Incorrect 9 ms 12160 KB Unexpected end of file - int32 expected