oj.uz

Submission #317213

# Submission time Handle Problem Language Result Execution time Memory
317213 2020-10-29T06:21:33 Z Seanliu Balanced Tree (info1cup18_balancedtree) C++14
0 / 100
 952 ms 61564 KB 
#include <iostream>
#include <vector>
using namespace std;

const int maxN = 3e5 + 326;
int T, N, col[maxN], u, v, dep[maxN], md[maxN][2], ans;
vector<int> adj[maxN];

void dfs(int p = 1, int u = 1){
	dep[u] = dep[p] + 1;
	for(int v : adj[u]) if(p != v){
		dfs(u, v);
		if(!md[u][0]){
			md[u][0] = md[v][0];
		} else {
			ans = max(ans, md[u][0] + md[v][0] - 2 * dep[u]); 
			md[u][0] = max(md[u][0], md[v][0]);
		}
		if(!md[u][1]){
			md[u][1] = md[v][1];
		} else {
			ans = max(ans, md[u][1] + md[v][1] - 2 * dep[u]); 
			md[u][1] = max(md[u][1], md[v][1]);
		}
	}
}

void solve(){
	cin >> N;
	ans = 0;
	for(int i = 0; i < N - 1; i++){
		cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	int hasz = 0, haso = 0;
	for(int i = 1; i <= N; i++){
		cin >> col[i];
		(col[i] ? hasz : haso) += 1;
	}
	if(hasz < 2 || haso < 2){
		cout << -1 << endl;
	} else {
		dfs();
		cout << ans << endl;
		for(int i = 1; i <= N; i++) cout << col[i] << " \n"[i == N];
	}
	for(int i = 1; i <= N; i++){
		vector<int>().swap(adj[i]);
		md[i][0] = md[i][1] = 0;
		dep[i] = 0;
	}
}

int main(){
	cin >> T;
	while(T--){
		solve();
	}
}

Subtask #1
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 7424 KB Output isn't correct
2 Incorrect 16 ms 7424 KB Output isn't correct

Subtask #2
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 125 ms 7556 KB Output isn't correct
2 Incorrect 182 ms 9976 KB Output isn't correct
3 Incorrect 172 ms 8056 KB Output isn't correct

Subtask #3
0.0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 136 ms 7672 KB Output isn't correct
2 Incorrect 191 ms 18168 KB Output isn't correct
3 Incorrect 142 ms 11948 KB Output isn't correct

Subtask #4
0.0 / 45.0

# Verdict Execution time Memory Grader output
1 Incorrect 168 ms 8548 KB Output isn't correct
2 Incorrect 138 ms 7672 KB Output isn't correct
3 Incorrect 141 ms 7800 KB Output isn't correct
4 Incorrect 119 ms 7672 KB Output isn't correct
5 Incorrect 118 ms 7544 KB Output isn't correct
6 Incorrect 150 ms 7800 KB Output isn't correct
7 Incorrect 139 ms 7672 KB Output isn't correct
8 Incorrect 119 ms 7544 KB Output isn't correct
9 Incorrect 119 ms 7544 KB Output isn't correct

Subtask #5
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 7424 KB Output isn't correct
2 Incorrect 16 ms 7424 KB Output isn't correct
3 Incorrect 125 ms 7556 KB Output isn't correct
4 Incorrect 182 ms 9976 KB Output isn't correct
5 Incorrect 172 ms 8056 KB Output isn't correct
6 Incorrect 136 ms 7672 KB Output isn't correct
7 Incorrect 191 ms 18168 KB Output isn't correct
8 Incorrect 142 ms 11948 KB Output isn't correct
9 Incorrect 168 ms 8548 KB Output isn't correct
10 Incorrect 138 ms 7672 KB Output isn't correct
11 Incorrect 141 ms 7800 KB Output isn't correct
12 Incorrect 119 ms 7672 KB Output isn't correct
13 Incorrect 118 ms 7544 KB Output isn't correct
14 Incorrect 150 ms 7800 KB Output isn't correct
15 Incorrect 139 ms 7672 KB Output isn't correct
16 Incorrect 119 ms 7544 KB Output isn't correct
17 Incorrect 119 ms 7544 KB Output isn't correct
18 Incorrect 753 ms 9168 KB Output isn't correct
19 Incorrect 952 ms 13304 KB Output isn't correct
20 Incorrect 574 ms 8440 KB Output isn't correct
21 Runtime error 699 ms 51704 KB Execution killed with signal 11 (could be triggered by violating memory limits)
22 Runtime error 831 ms 61564 KB Execution killed with signal 11 (could be triggered by violating memory limits)