oj.uz

Submission #317216

# Submission time Handle Problem Language Result Execution time Memory
317216 2020-10-29T06:23:14 Z Seanliu Balanced Tree (info1cup18_balancedtree) C++14
0 / 100
 1000 ms 56696 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]);
		}
		ans = max(ans, md[v][col[u]] - dep[u]);
	}
}

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 126 ms 7672 KB Output isn't correct
2 Incorrect 180 ms 9976 KB Output isn't correct
3 Incorrect 152 ms 8056 KB Output isn't correct

Subtask #3
0.0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 134 ms 7672 KB Output isn't correct
2 Incorrect 199 ms 18212 KB Output isn't correct
3 Incorrect 165 ms 11896 KB Output isn't correct

Subtask #4
0.0 / 45.0

# Verdict Execution time Memory Grader output
1 Incorrect 168 ms 8568 KB Output isn't correct
2 Incorrect 149 ms 7636 KB Output isn't correct
3 Incorrect 160 ms 7672 KB Output isn't correct
4 Incorrect 131 ms 7544 KB Output isn't correct
5 Incorrect 117 ms 7544 KB Output isn't correct
6 Incorrect 153 ms 7800 KB Output isn't correct
7 Incorrect 138 ms 7672 KB Output isn't correct
8 Incorrect 123 ms 7636 KB Output isn't correct
9 Incorrect 118 ms 7620 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 126 ms 7672 KB Output isn't correct
4 Incorrect 180 ms 9976 KB Output isn't correct
5 Incorrect 152 ms 8056 KB Output isn't correct
6 Incorrect 134 ms 7672 KB Output isn't correct
7 Incorrect 199 ms 18212 KB Output isn't correct
8 Incorrect 165 ms 11896 KB Output isn't correct
9 Incorrect 168 ms 8568 KB Output isn't correct
10 Incorrect 149 ms 7636 KB Output isn't correct
11 Incorrect 160 ms 7672 KB Output isn't correct
12 Incorrect 131 ms 7544 KB Output isn't correct
13 Incorrect 117 ms 7544 KB Output isn't correct
14 Incorrect 153 ms 7800 KB Output isn't correct
15 Incorrect 138 ms 7672 KB Output isn't correct
16 Incorrect 123 ms 7636 KB Output isn't correct
17 Incorrect 118 ms 7620 KB Output isn't correct
18 Incorrect 780 ms 9028 KB Output isn't correct
19 Incorrect 1000 ms 13316 KB Output isn't correct
20 Incorrect 584 ms 8236 KB Output isn't correct
21 Runtime error 723 ms 51520 KB Execution killed with signal 11 (could be triggered by violating memory limits)
22 Runtime error 852 ms 56696 KB Execution killed with signal 11 (could be triggered by violating memory limits)