oj.uz

Submission #317101

# Submission time Handle Problem Language Result Execution time Memory
317101 2020-10-29T03:25:43 Z 8e7 Balanced Tree (info1cup18_balancedtree) C++14
0 / 100
 382 ms 14584 KB 
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#define ll long long
#define pii pair<int, int>
#define ff first
#define ss second
#define maxn 100005
using namespace std;
const int inf = 8e7;
vector<int> adj[maxn];
int c[maxn];
pii val[maxn];
pii dfs(int n, int par) {
	pii ret = make_pair(inf, inf);
	for (int v:adj[n]) {
		if (v != par) {
			pii res = dfs(v, n);
			ret.ff = min(ret.ff, res.ff + 1);
			ret.ss = min(ret.ss, res.ss + 1);
		}
	}
	val[n] = ret;
	if (c[n]) ret.ss = 0;
	else ret.ff = 0;
	return ret;
}
void dfs2(int n, int par, pii cur) {
	val[n].ff = min(val[n].ff, cur.ff);
	val[n].ss = min(val[n].ss, cur.ss);
	cur.ff = min(cur.ff, val[n].ff) + 1;
	cur.ss = min(cur.ss, val[n].ss) + 1;
	for (int v:adj[n]) {
		if (v != par) {
			dfs2(v, n, cur);
		}
	}
}
int main() {
	ios_base::sync_with_stdio(0);cin.tie(0);
	int t;
	cin >> t;
	while (t--) {
		int n;
		cin >> n;
		for (int i = 1;i <= n;i++) c[i] = 0, adj[i].clear();
		for (int i = 0;i < n - 1;i++) {
			int a, b;
			cin >> a >> b;
			adj[a].push_back(b);
			adj[b].push_back(a);
		}
		int c0 = 0, c1 = 0;
		for (int i = 1;i <= n;i++) {
			cin >> c[i];
			if (c[i]) c1++;
			else c0++;
		}
		if (c0 == 1 || c1 == 1) {
			cout << -1 << endl;
		} else {
			dfs(1, 0);
			pii temp = make_pair(inf, inf);
			dfs2(1, 0, temp);
			int ans = 0;
			if (c0) {
				for (int i = 1;i <= n;i++) ans = max(ans, val[i].ff);
			}
			if (c1) {
				for (int i = 1;i <= n;i++) ans = max(ans, val[i].ss);
			}
			cout << ans << endl;
			for (int i = 1;i <= n;i++) cout << c[i] << " ";
			cout << endl;
		}
	}
}

Subtask #1
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 2688 KB Output isn't correct
2 Incorrect 7 ms 2688 KB Invalid color

Subtask #2
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 39 ms 2940 KB Output isn't correct
2 Incorrect 61 ms 5112 KB Output isn't correct
3 Incorrect 43 ms 3448 KB Output isn't correct

Subtask #3
0.0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 40 ms 3328 KB Output isn't correct
2 Incorrect 72 ms 14584 KB Output isn't correct
3 Incorrect 42 ms 7800 KB Invalid color

Subtask #4
0.0 / 45.0

# Verdict Execution time Memory Grader output
1 Incorrect 53 ms 4088 KB Output isn't correct
2 Incorrect 39 ms 3320 KB Invalid color
3 Incorrect 38 ms 3320 KB Invalid color
4 Incorrect 37 ms 3456 KB Invalid color
5 Incorrect 32 ms 3320 KB Output isn't correct
6 Incorrect 41 ms 3576 KB Output isn't correct
7 Incorrect 39 ms 3448 KB Invalid color
8 Incorrect 37 ms 3320 KB Invalid color
9 Incorrect 32 ms 3328 KB Output isn't correct

Subtask #5
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 2688 KB Output isn't correct
2 Incorrect 7 ms 2688 KB Invalid color
3 Incorrect 39 ms 2940 KB Output isn't correct
4 Incorrect 61 ms 5112 KB Output isn't correct
5 Incorrect 43 ms 3448 KB Output isn't correct
6 Incorrect 40 ms 3328 KB Output isn't correct
7 Incorrect 72 ms 14584 KB Output isn't correct
8 Incorrect 42 ms 7800 KB Invalid color
9 Incorrect 53 ms 4088 KB Output isn't correct
10 Incorrect 39 ms 3320 KB Invalid color
11 Incorrect 38 ms 3320 KB Invalid color
12 Incorrect 37 ms 3456 KB Invalid color
13 Incorrect 32 ms 3320 KB Output isn't correct
14 Incorrect 41 ms 3576 KB Output isn't correct
15 Incorrect 39 ms 3448 KB Invalid color
16 Incorrect 37 ms 3320 KB Invalid color
17 Incorrect 32 ms 3328 KB Output isn't correct
18 Incorrect 195 ms 4600 KB Output isn't correct
19 Incorrect 382 ms 8824 KB Output isn't correct
20 Incorrect 175 ms 4216 KB Output isn't correct
21 Runtime error 6 ms 6016 KB Execution killed with signal 11 (could be triggered by violating memory limits)
22 Runtime error 72 ms 6904 KB Execution killed with signal 11 (could be triggered by violating memory limits)