oj.uz

Submission #317219

# Submission time Handle Problem Language Result Execution time Memory
317219 2020-10-29T06:25:21 Z Seanliu Balanced Tree (info1cup18_balancedtree) C++14
0 / 100
 1031 ms 51448 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;
	md[u][col[u]] = dep[u];
	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 129 ms 7544 KB Output isn't correct
2 Incorrect 192 ms 9976 KB Output isn't correct
3 Incorrect 156 ms 8056 KB Output isn't correct

Subtask #3
0.0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 138 ms 7800 KB Output isn't correct
2 Incorrect 196 ms 18168 KB Output isn't correct
3 Incorrect 156 ms 11896 KB Output isn't correct

Subtask #4
0.0 / 45.0

# Verdict Execution time Memory Grader output
1 Incorrect 184 ms 8568 KB Output isn't correct
2 Incorrect 141 ms 7676 KB Output isn't correct
3 Incorrect 145 ms 7672 KB Output isn't correct
4 Incorrect 122 ms 7544 KB Output isn't correct
5 Incorrect 121 ms 7544 KB Output isn't correct
6 Incorrect 151 ms 7800 KB Output isn't correct
7 Incorrect 139 ms 7672 KB Output isn't correct
8 Incorrect 126 ms 7544 KB Output isn't correct
9 Incorrect 121 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 129 ms 7544 KB Output isn't correct
4 Incorrect 192 ms 9976 KB Output isn't correct
5 Incorrect 156 ms 8056 KB Output isn't correct
6 Incorrect 138 ms 7800 KB Output isn't correct
7 Incorrect 196 ms 18168 KB Output isn't correct
8 Incorrect 156 ms 11896 KB Output isn't correct
9 Incorrect 184 ms 8568 KB Output isn't correct
10 Incorrect 141 ms 7676 KB Output isn't correct
11 Incorrect 145 ms 7672 KB Output isn't correct
12 Incorrect 122 ms 7544 KB Output isn't correct
13 Incorrect 121 ms 7544 KB Output isn't correct
14 Incorrect 151 ms 7800 KB Output isn't correct
15 Incorrect 139 ms 7672 KB Output isn't correct
16 Incorrect 126 ms 7544 KB Output isn't correct
17 Incorrect 121 ms 7544 KB Output isn't correct
18 Incorrect 781 ms 9080 KB Output isn't correct
19 Incorrect 1031 ms 13304 KB Output isn't correct
20 Incorrect 608 ms 8396 KB Output isn't correct
21 Runtime error 745 ms 51448 KB Execution killed with signal 11 (could be triggered by violating memory limits)
22 Runtime error 308 ms 17272 KB Execution killed with signal 11 (could be triggered by violating memory limits)