oj.uz

Submission #360126

# Submission time Handle Problem Language Result Execution time Memory
360126 2021-01-27T13:58:49 Z Mlxa Balanced Tree (info1cup18_balancedtree) C++14
0 / 100
 388 ms 18408 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 check(int value) {
	queue<int> q;
	fill_n(dist, n, N);
	for (int i = 0; i < n; ++i) {
		if (c[i] == value) {
			dist[i] = 0;
			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) {
				dist[u] = dist[v] + 1;
				q.push(u);
			}
		}
	}
	int answer = 0;
	for (int i = 0; i < n; ++i) {
		for (int j : g[i]) {
			answer = max(answer, dist[i] + 1 + dist[j]);
		}
	}
	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];
	}
	cout << max(check(0), check(1)) << "\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 4 ms 2796 KB Output isn't correct
2 Incorrect 5 ms 2796 KB Output isn't correct

Subtask #2
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 39 ms 3692 KB Output isn't correct
2 Incorrect 61 ms 7404 KB Output isn't correct
3 Incorrect 46 ms 4844 KB Output isn't correct

Subtask #3
0.0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 38 ms 3948 KB Output isn't correct
2 Incorrect 81 ms 9452 KB Output isn't correct
3 Incorrect 40 ms 5996 KB Invalid color

Subtask #4
0.0 / 45.0

# Verdict Execution time Memory Grader output
1 Incorrect 53 ms 5740 KB Output isn't correct
2 Incorrect 42 ms 4076 KB Output isn't correct
3 Incorrect 42 ms 4204 KB Output isn't correct
4 Incorrect 37 ms 3692 KB Output isn't correct
5 Incorrect 35 ms 3948 KB Output isn't correct
6 Incorrect 52 ms 4588 KB Output isn't correct
7 Incorrect 43 ms 4076 KB Output isn't correct
8 Incorrect 38 ms 3712 KB Output isn't correct
9 Incorrect 35 ms 3948 KB Output isn't correct

Subtask #5
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 2796 KB Output isn't correct
2 Incorrect 5 ms 2796 KB Output isn't correct
3 Incorrect 39 ms 3692 KB Output isn't correct
4 Incorrect 61 ms 7404 KB Output isn't correct
5 Incorrect 46 ms 4844 KB Output isn't correct
6 Incorrect 38 ms 3948 KB Output isn't correct
7 Incorrect 81 ms 9452 KB Output isn't correct
8 Incorrect 40 ms 5996 KB Invalid color
9 Incorrect 53 ms 5740 KB Output isn't correct
10 Incorrect 42 ms 4076 KB Output isn't correct
11 Incorrect 42 ms 4204 KB Output isn't correct
12 Incorrect 37 ms 3692 KB Output isn't correct
13 Incorrect 35 ms 3948 KB Output isn't correct
14 Incorrect 52 ms 4588 KB Output isn't correct
15 Incorrect 43 ms 4076 KB Output isn't correct
16 Incorrect 38 ms 3712 KB Output isn't correct
17 Incorrect 35 ms 3948 KB Output isn't correct
18 Incorrect 232 ms 11004 KB Output isn't correct
19 Incorrect 388 ms 18408 KB Output isn't correct
20 Incorrect 178 ms 7936 KB Output isn't correct
21 Runtime error 7 ms 5740 KB Execution killed with signal 11
22 Runtime error 79 ms 8684 KB Execution killed with signal 11