oj.uz

Submission #360130

# Submission time Handle Problem Language Result Execution time Memory
360130 2021-01-27T14:09:04 Z Mlxa Balanced Tree (info1cup18_balancedtree) C++14
13 / 100
 635 ms 20844 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 7404 KB Invalid color
2 Incorrect 9 ms 7404 KB Invalid color

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 7660 KB Output is correct
2 Correct 116 ms 12780 KB Output is correct
3 Correct 67 ms 8940 KB Output is correct

Subtask #3
0.0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 54 ms 7680 KB Output isn't correct
2 Incorrect 139 ms 18168 KB Output isn't correct
3 Incorrect 55 ms 11224 KB Invalid color

Subtask #4
0.0 / 45.0

# Verdict Execution time Memory Grader output
1 Incorrect 74 ms 10184 KB Output isn't correct
2 Incorrect 65 ms 7788 KB Invalid color
3 Incorrect 63 ms 7788 KB Invalid color
4 Incorrect 50 ms 7660 KB Invalid color
5 Incorrect 49 ms 7788 KB Output isn't correct
6 Incorrect 59 ms 8248 KB Output isn't correct
7 Incorrect 63 ms 7916 KB Invalid color
8 Incorrect 50 ms 7660 KB Output isn't correct
9 Incorrect 47 ms 7696 KB Invalid color

Subtask #5
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 7404 KB Invalid color
2 Incorrect 9 ms 7404 KB Invalid color
3 Correct 64 ms 7660 KB Output is correct
4 Correct 116 ms 12780 KB Output is correct
5 Correct 67 ms 8940 KB Output is correct
6 Incorrect 54 ms 7680 KB Output isn't correct
7 Incorrect 139 ms 18168 KB Output isn't correct
8 Incorrect 55 ms 11224 KB Invalid color
9 Incorrect 74 ms 10184 KB Output isn't correct
10 Incorrect 65 ms 7788 KB Invalid color
11 Incorrect 63 ms 7788 KB Invalid color
12 Incorrect 50 ms 7660 KB Invalid color
13 Incorrect 49 ms 7788 KB Output isn't correct
14 Incorrect 59 ms 8248 KB Output isn't correct
15 Incorrect 63 ms 7916 KB Invalid color
16 Incorrect 50 ms 7660 KB Output isn't correct
17 Incorrect 47 ms 7696 KB Invalid color
18 Incorrect 293 ms 9708 KB Output isn't correct
19 Incorrect 635 ms 20844 KB Output isn't correct
20 Incorrect 231 ms 8412 KB Output isn't correct
21 Runtime error 15 ms 15272 KB Execution killed with signal 11
22 Runtime error 118 ms 16108 KB Execution killed with signal 11