oj.uz

Submission #317130

# Submission time Handle Problem Language Result Execution time Memory
317130 2020-10-29T03:55:54 Z 8e7 Balanced Tree (info1cup18_balancedtree) C++14
0 / 100
 4000 ms 35440 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 500005
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);
	for (int v:adj[n]) {
		if (v != par) {
			pii upd = cur;
			for (int u:adj[n]) {
				if (u != par && u != v) {
					upd.ff = min(upd.ff, val[u].ff + 1);
					upd.ss = min(upd.ss, val[u].ss + 1);
				}
			}
			if (c[n]) {
				upd.ss = 0;
			} else {
				upd.ff = 0;
			}
			upd.ff++, upd.ss++;
			dfs2(v, n, upd);
		}
	}
}
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;
		vector<int> pos;
		for (int i = 1;i <= n;i++) {
			cin >> c[i];
			if (c[i] == 1) c1++;
			else if (c[i] == 0) c0++;
			else pos.push_back(i);
		}
		int s = pos.size();
		int ans = inf, ind = 0;
		if (s) {
			for (int i = 0;i < (1<<s);i++) {
				for (int j = 0;j < s;j++) {
					c[pos[j]] = (i & (1<<j)) ? (c1++, 1) : (c0++, 0);
				}
				dfs(1, 0);
				pii temp = make_pair(inf, inf);
				dfs2(1, 0, temp);
				int num = 0;
				if (c0) {
					for (int i = 1;i <= n;i++) {
						num = max(num, val[i].ff);
						//cout << val[i].ff << " " << val[i].ss << endl;
					}
				}
				if (c1) {
					for (int i = 1;i <= n;i++) num = max(num, val[i].ss);
				}
				if (num < ans) {
					ans = num, ind = i;
				}
			}
			for (int j = 0;j < s;j++) {
				c[pos[j]] = (ind & (1<<j)) ? 1 : 0;
			}
		} else {
			dfs(1, 0);
			pii temp = make_pair(inf, inf);
			dfs2(1, 0, temp);
			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 << val[i].ff << " " << val[i].ss << endl;
			cout << c[i] << " ";
		}
		cout << endl;
	}
}

Subtask #1
0.0 / 10.0

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

Subtask #2
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 47 ms 12408 KB Output isn't correct
2 Incorrect 76 ms 14584 KB Output isn't correct
3 Incorrect 52 ms 12792 KB Output isn't correct

Subtask #3
0.0 / 26.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4051 ms 12160 KB Time limit exceeded
2 Incorrect 1827 ms 24184 KB Output isn't correct
3 Execution timed out 4075 ms 17144 KB Time limit exceeded

Subtask #4
0.0 / 45.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4038 ms 12928 KB Time limit exceeded
2 Execution timed out 4062 ms 12288 KB Time limit exceeded
3 Execution timed out 4045 ms 12160 KB Time limit exceeded
4 Execution timed out 4066 ms 12160 KB Time limit exceeded
5 Execution timed out 4019 ms 12288 KB Time limit exceeded
6 Execution timed out 4089 ms 12416 KB Time limit exceeded
7 Execution timed out 4022 ms 12160 KB Time limit exceeded
8 Execution timed out 4019 ms 12280 KB Time limit exceeded
9 Execution timed out 4022 ms 12160 KB Time limit exceeded

Subtask #5
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 12160 KB Output isn't correct
2 Incorrect 17 ms 12160 KB Output isn't correct
3 Incorrect 47 ms 12408 KB Output isn't correct
4 Incorrect 76 ms 14584 KB Output isn't correct
5 Incorrect 52 ms 12792 KB Output isn't correct
6 Execution timed out 4051 ms 12160 KB Time limit exceeded
7 Incorrect 1827 ms 24184 KB Output isn't correct
8 Execution timed out 4075 ms 17144 KB Time limit exceeded
9 Execution timed out 4038 ms 12928 KB Time limit exceeded
10 Execution timed out 4062 ms 12288 KB Time limit exceeded
11 Execution timed out 4045 ms 12160 KB Time limit exceeded
12 Execution timed out 4066 ms 12160 KB Time limit exceeded
13 Execution timed out 4019 ms 12288 KB Time limit exceeded
14 Execution timed out 4089 ms 12416 KB Time limit exceeded
15 Execution timed out 4022 ms 12160 KB Time limit exceeded
16 Execution timed out 4019 ms 12280 KB Time limit exceeded
17 Execution timed out 4022 ms 12160 KB Time limit exceeded
18 Execution timed out 4019 ms 12544 KB Time limit exceeded
19 Execution timed out 4017 ms 16508 KB Time limit exceeded
20 Execution timed out 4034 ms 12284 KB Time limit exceeded
21 Incorrect 794 ms 35440 KB Output isn't correct
22 Execution timed out 4019 ms 12160 KB Time limit exceeded