oj.uz

Submission #317065

# Submission time Handle Problem Language Result Execution time Memory
317065 2020-10-29T02:19:39 Z Kevin_Zhang_TW Balanced Tree (info1cup18_balancedtree) C++17
0 / 100
 369 ms 37752 KB 
#include<bits/stdc++.h>
#define pb emplace_back
#define AI(i) begin(i), end(i)
using namespace std;
using ll = long long;
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] : ", args)
void kout() { cerr << endl; }
template<class T, class ...U>
void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
void debug(auto L, auto R) { while (L != R) cerr << *L << " \n"[next(L) == R], ++L; }
#else
#define debug(...) 0
#define DE(...) 0
#endif
const int MAX_N = 500010, inf = 1e9;
int n, c[MAX_N];
vector<int> edge[MAX_N];
void clear() {
	for (int i = 1; edge[i].size() ; ++i)
		edge[i].clear();
}
int dis[MAX_N], sz[MAX_N];
bool ban[MAX_N];
int dfs_sz(int x, int lst = -1) {
	sz[x] = 1;
	for (int u : edge[x]) if (u != lst && !ban[u])
		sz[x] += dfs_sz(u, x);
	return sz[x];
}
int dfs_cen(int x, int allsz, int lst = -1) {
	for (int u : edge[x]) if (u != lst && !ban[u])
		if (sz[u] * 2 > allsz)
			return dfs_cen(u, allsz, x);
	return x;
}

void chmin(int &v, int val) { v = min(v, val); }
int min_dep[2];
void dfs_update(int x, int lst = -1) {
	static int d;
	if (ban[x]) return;
	++d;
	chmin(dis[x], min_dep[c[x]] + d);
	chmin(min_dep[c[x]], d);
	for (int u : edge[x]) if (u != lst)
		dfs_update(u, x);
	--d;
}
void dfs_solve(int side) {
	if (ban[side]) return;
	int cen = dfs_cen(side, dfs_sz(side));

	min_dep[0] = min_dep[1] = inf;
	
	min_dep[ c[cen] ] = 0;
	for (int u : edge[cen]) 
		dfs_update(u);

	min_dep[0] = min_dep[1] = inf;

	reverse(AI(edge[cen]));

	for (int u : edge[cen])
		dfs_update(u);

	chmin(dis[cen], min_dep[c[cen]]);

	ban[cen] = true;
	for (int u : edge[cen])
		dfs_solve(u);
}
	
int cal() {
	for (int i = 1;i <= n;++i) {
		dis[i] = inf;
		ban[i] = false;
	}
	dfs_solve(1);
	return *max_element(dis+1, dis+n+1);
}
void solve() {
	cin >> n;
	clear();
	for (int a, b, i = 1;i < n;++i) {
		cin >> a >> b;
		edge[a].pb(b);
		edge[b].pb(a);
	}

	for (int i = 1;i <= n;++i)
		cin >> c[i];

	int cn = count(c+1, c+n+1, -1), c0 = count(c+1, c+n+1, 0), c1 = count(c+1, c+n+1, 1);

	if (min(c0, c1) == 1 && cn == 0) 
		return cout << -1 << '\n', void();

	if (cn == 0) {
		cout << cal() << '\n';
		for (int i = 1;i <= n;++i)
			cout << c[i] << " \n"[i==n];
	}
	else
		cout << -1 << '\n';
}
int32_t main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	int T;
	cin >> T;
	while (T--)
		solve();
}

Subtask #1
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 12160 KB Output isn't correct
2 Incorrect 10 ms 12160 KB Output isn't correct

Subtask #2
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 91 ms 13048 KB Output isn't correct
2 Incorrect 369 ms 15992 KB Output isn't correct
3 Incorrect 227 ms 14072 KB Output isn't correct

Subtask #3
0.0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 30 ms 13056 KB Output isn't correct
2 Incorrect 52 ms 17016 KB Output isn't correct
3 Incorrect 35 ms 14588 KB Output isn't correct

Subtask #4
0.0 / 45.0

# Verdict Execution time Memory Grader output
1 Incorrect 42 ms 14200 KB Output isn't correct
2 Incorrect 32 ms 13304 KB Output isn't correct
3 Incorrect 33 ms 13304 KB Output isn't correct
4 Incorrect 29 ms 12928 KB Output isn't correct
5 Incorrect 28 ms 13048 KB Output isn't correct
6 Incorrect 35 ms 13568 KB Output isn't correct
7 Incorrect 32 ms 13176 KB Output isn't correct
8 Incorrect 30 ms 12928 KB Output isn't correct
9 Incorrect 28 ms 13056 KB Output isn't correct

Subtask #5
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 12160 KB Output isn't correct
2 Incorrect 10 ms 12160 KB Output isn't correct
3 Incorrect 91 ms 13048 KB Output isn't correct
4 Incorrect 369 ms 15992 KB Output isn't correct
5 Incorrect 227 ms 14072 KB Output isn't correct
6 Incorrect 30 ms 13056 KB Output isn't correct
7 Incorrect 52 ms 17016 KB Output isn't correct
8 Incorrect 35 ms 14588 KB Output isn't correct
9 Incorrect 42 ms 14200 KB Output isn't correct
10 Incorrect 32 ms 13304 KB Output isn't correct
11 Incorrect 33 ms 13304 KB Output isn't correct
12 Incorrect 29 ms 12928 KB Output isn't correct
13 Incorrect 28 ms 13048 KB Output isn't correct
14 Incorrect 35 ms 13568 KB Output isn't correct
15 Incorrect 32 ms 13176 KB Output isn't correct
16 Incorrect 30 ms 12928 KB Output isn't correct
17 Incorrect 28 ms 13056 KB Output isn't correct
18 Incorrect 138 ms 18552 KB Output isn't correct
19 Incorrect 212 ms 22776 KB Output isn't correct
20 Incorrect 113 ms 15992 KB Output isn't correct
21 Incorrect 327 ms 37752 KB Output isn't correct
22 Incorrect 186 ms 29816 KB Output isn't correct