oj.uz

Submission #360128

# Submission time Handle Problem Language Result Execution time Memory
360128 2021-01-27T14:02:52 Z Mlxa Balanced Tree (info1cup18_balancedtree) C++14
0 / 100
 448 ms 12316 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];

int check(int value) {
	queue<int> q;
	fill_n(dist, n, N);
	fill_n(who, n, -1);
	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]) {
				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 5 ms 2668 KB Output isn't correct
2 Incorrect 7 ms 2668 KB Output isn't correct

Subtask #2
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 42 ms 2924 KB Output isn't correct
2 Incorrect 74 ms 6508 KB Output isn't correct
3 Incorrect 58 ms 3820 KB Output isn't correct

Subtask #3
0.0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 39 ms 2956 KB Output isn't correct
2 Incorrect 75 ms 8940 KB Output isn't correct
3 Incorrect 47 ms 5228 KB Invalid color

Subtask #4
0.0 / 45.0

# Verdict Execution time Memory Grader output
1 Incorrect 60 ms 4716 KB Output isn't correct
2 Incorrect 44 ms 3052 KB Output isn't correct
3 Incorrect 44 ms 3404 KB Invalid color
4 Incorrect 39 ms 2924 KB Invalid color
5 Incorrect 38 ms 3120 KB Output isn't correct
6 Incorrect 46 ms 3436 KB Invalid color
7 Incorrect 44 ms 3052 KB Invalid color
8 Incorrect 38 ms 2924 KB Output isn't correct
9 Incorrect 35 ms 3052 KB Invalid color

Subtask #5
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 2668 KB Output isn't correct
2 Incorrect 7 ms 2668 KB Output isn't correct
3 Incorrect 42 ms 2924 KB Output isn't correct
4 Incorrect 74 ms 6508 KB Output isn't correct
5 Incorrect 58 ms 3820 KB Output isn't correct
6 Incorrect 39 ms 2956 KB Output isn't correct
7 Incorrect 75 ms 8940 KB Output isn't correct
8 Incorrect 47 ms 5228 KB Invalid color
9 Incorrect 60 ms 4716 KB Output isn't correct
10 Incorrect 44 ms 3052 KB Output isn't correct
11 Incorrect 44 ms 3404 KB Invalid color
12 Incorrect 39 ms 2924 KB Invalid color
13 Incorrect 38 ms 3120 KB Output isn't correct
14 Incorrect 46 ms 3436 KB Invalid color
15 Incorrect 44 ms 3052 KB Invalid color
16 Incorrect 38 ms 2924 KB Output isn't correct
17 Incorrect 35 ms 3052 KB Invalid color
18 Incorrect 233 ms 5104 KB Output isn't correct
19 Incorrect 448 ms 12316 KB Output isn't correct
20 Incorrect 185 ms 3948 KB Output isn't correct
21 Runtime error 8 ms 5740 KB Execution killed with signal 11
22 Runtime error 81 ms 6508 KB Execution killed with signal 11