oj.uz

Submission #317209

# Submission time Handle Problem Language Result Execution time Memory
317209 2020-10-29T06:20:01 Z Seanliu Balanced Tree (info1cup18_balancedtree) C++14
0 / 100
 971 ms 61336 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;
	}
}

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

Subtask #1
0.0 / 10.0

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

Subtask #2
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 128 ms 7544 KB Output isn't correct
2 Incorrect 186 ms 9976 KB Output isn't correct
3 Incorrect 157 ms 8056 KB Output isn't correct

Subtask #3
0.0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 142 ms 7600 KB Output isn't correct
2 Incorrect 190 ms 18168 KB Output isn't correct
3 Incorrect 162 ms 11892 KB Output isn't correct

Subtask #4
0.0 / 45.0

# Verdict Execution time Memory Grader output
1 Incorrect 176 ms 8628 KB Output isn't correct
2 Incorrect 155 ms 7628 KB Output isn't correct
3 Incorrect 140 ms 7672 KB Output isn't correct
4 Incorrect 123 ms 7544 KB Output isn't correct
5 Incorrect 122 ms 7544 KB Output isn't correct
6 Incorrect 149 ms 7776 KB Output isn't correct
7 Incorrect 140 ms 7648 KB Output isn't correct
8 Incorrect 118 ms 7672 KB Output isn't correct
9 Incorrect 117 ms 7544 KB Output isn't correct

Subtask #5
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 7424 KB Output isn't correct
2 Incorrect 18 ms 7424 KB Output isn't correct
3 Incorrect 128 ms 7544 KB Output isn't correct
4 Incorrect 186 ms 9976 KB Output isn't correct
5 Incorrect 157 ms 8056 KB Output isn't correct
6 Incorrect 142 ms 7600 KB Output isn't correct
7 Incorrect 190 ms 18168 KB Output isn't correct
8 Incorrect 162 ms 11892 KB Output isn't correct
9 Incorrect 176 ms 8628 KB Output isn't correct
10 Incorrect 155 ms 7628 KB Output isn't correct
11 Incorrect 140 ms 7672 KB Output isn't correct
12 Incorrect 123 ms 7544 KB Output isn't correct
13 Incorrect 122 ms 7544 KB Output isn't correct
14 Incorrect 149 ms 7776 KB Output isn't correct
15 Incorrect 140 ms 7648 KB Output isn't correct
16 Incorrect 118 ms 7672 KB Output isn't correct
17 Incorrect 117 ms 7544 KB Output isn't correct
18 Incorrect 751 ms 8952 KB Output isn't correct
19 Incorrect 971 ms 13308 KB Output isn't correct
20 Incorrect 577 ms 8312 KB Output isn't correct
21 Runtime error 705 ms 51576 KB Execution killed with signal 11 (could be triggered by violating memory limits)
22 Runtime error 843 ms 61336 KB Execution killed with signal 11 (could be triggered by violating memory limits)