Submission #317101

#	Time	Username	Problem	Language	Result	Execution time	Memory
317101		8e7	Balanced Tree (info1cup18_balancedtree)	C++14	0 / 100	382 ms	14584 KiB

balancedtree

#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 100005
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);
	cur.ff = min(cur.ff, val[n].ff) + 1;
	cur.ss = min(cur.ss, val[n].ss) + 1;
	for (int v:adj[n]) {
		if (v != par) {
			dfs2(v, n, cur);
		}
	}
}
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;
		for (int i = 1;i <= n;i++) {
			cin >> c[i];
			if (c[i]) c1++;
			else c0++;
		}
		if (c0 == 1 || c1 == 1) {
			cout << -1 << endl;
		} else {
			dfs(1, 0);
			pii temp = make_pair(inf, inf);
			dfs2(1, 0, temp);
			int ans = 0;
			if (c0) {
				for (int i = 1;i <= n;i++) ans = max(ans, val[i].ff);
			}
			if (c1) {
				for (int i = 1;i <= n;i++) ans = max(ans, val[i].ss);
			}
			cout << ans << endl;
			for (int i = 1;i <= n;i++) cout << c[i] << " ";
			cout << endl;
		}
	}
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 13
• Subtask 3: 0 / 26
• Subtask 4: 0 / 45
• Subtask 5: 0 / 6