Submission #360130

#	Time	Username	Problem	Language	Result	Execution time	Memory
360130		Mlxa	Balanced Tree (info1cup18_balancedtree)	C++14	13 / 100	635 ms	20844 KiB

balancedtree

#ifdef LC
#include "pch.h"
#else
#include <bits/stdc++.h>
#endif
using namespace std;
using ll = long long;
#define int ll
#define all(x) x.begin(), x.end()
#define x first
#define y second
#define mp make_pair
#define mt make_tuple

const int N = 1e5 + 10;

int n;
vector<int> g[N];
int c[N];
int dist[N];
int who[N];
set<int> kek[N];

int check(int value) {
	queue<int> q;
	fill_n(dist, n, N);
	fill_n(who, n, -1);
	fill_n(kek, n, set<int>());

	for (int i = 0; i < n; ++i) {
		if (c[i] == value) {
			dist[i] = 0;
			who[i] = i;
			q.push(i);
		}
	}
	if (q.empty()) {
		return 0;
	}
	while (q.size()) {
		int v = q.front(); q.pop();
		for (int u : g[v]) {
			if (dist[u] > dist[v] + 1) {
				who[u] = who[v];
				dist[u] = dist[v] + 1;
				q.push(u);
			}
		}
	}
	int answer = 0;
	for (int i = 0; i < n; ++i) {
		for (int j : g[i]) {
			if (who[i] != who[j]) {
				int cur = dist[i] + 1 + dist[j];
				kek[who[i]].insert(cur);
				kek[who[j]].insert(cur);
			}
		}
	}
	for (int i = 0; i < n; ++i) {
		if (c[i] == value) {
			if (kek[i].empty()) {
				answer = N;
			} else {
				answer = max(answer, *kek[i].begin());
			}
		}
	}
	return answer;
}

void solve() {
	cin >> n;
	fill_n(g, n, vector<int>());
	for (int v, u, i = 0; i < n - 1; ++i) {
		cin >> v >> u;
		--v, --u;
		g[v].push_back(u);
		g[u].push_back(v);
	}
	for (int i = 0; i < n; ++i) {
		cin >> c[i];
	}
	int ans = max(check(0), check(1));
	if (ans == N) {
		cout << "-1\n";
		return;
	}
	cout << ans << "\n";
	for (int i = 0; i < n; ++i) {
		cout << c[i] << " ";
	}
	cout << "\n";
}

signed main() {
#ifdef LC
    assert(freopen("input.txt", "r", stdin));
#endif
    ios::sync_with_stdio(0); cin.tie(0);
    int tn;
    cin >> tn;
    while (tn--) {
    	solve();
    }
    return 0;
}

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