oj.uz

Submission #485752

# Submission time Handle Problem Language Result Execution time Memory
485752 2021-11-09T08:15:47 Z rk42745417 Balanced Tree (info1cup18_balancedtree) C++17
13 / 100
 263 ms 30216 KB 
#include <bits/stdc++.h>
using namespace std;

#define EmiliaMyWife ios::sync_with_stdio(0); cin.tie(0);
using ll = int64_t;
using ull = uint64_t;
using uint = uint32_t;
using ld = long double;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
const ll LINF = ll(2e18) + ll(1e15);
const double EPS = 1e-8;
static auto LamyIsCute = []() {
	EmiliaMyWife
	return 48763;
}();

signed main() {
	int t;
	cin >> t;
	while(t--) {
		int n;
		cin >> n;
		vector<vector<int>> edge(n + 1);
		for(int i = 1; i < n; i++) {
			int u, v;
			cin >> u >> v;
			edge[u].push_back(v);
			edge[v].push_back(u);
		}
		vector<int> arr(n + 1);
		for(int i = 1; i <= n; i++) {
			cin >> arr[i];
			if(arr[i] == -1)
				return 0;
		}
		int ans = 0;
		vector<int> dis(n + 1, INF);
		function<void(int, int, int)> dfs = [&](int u, int p, int c) {
			for(int v : edge[u]) {
				if(v == p)
					continue;
				dfs(v, u, c);
				dis[u] = min(dis[u], dis[v] + 1);
				if(arr[v] == c)
					dis[u] = 1;
			}
		};
		function<void(int, int, int, int)> dfs2 = [&](int u, int p, int c, int d) {
			//cout << c << ' ' << d << ' ' << dis[u] << '\n';
			if(arr[u] == c)
				ans = max(ans, min(dis[u], d));
			if(arr[u] == c)
				d = 0;
			multiset<int> has;
			has.insert(d);
			for(int v : edge[u]) {
				if(v == p)
					continue;
				if(arr[v] == c)
					has.insert(1);
				else
					has.insert(dis[v] + 1);
			}
			for(int v : edge[u]) {
				if(v == p)
					continue;
				if(arr[v] == c)
					has.erase(has.lower_bound(1));
				else
					has.erase(has.lower_bound(dis[v] + 1));
				dfs2(v, u, c, *has.begin() + 1);
				if(arr[v] == c)
					has.insert(1);
				else
					has.insert(dis[v] + 1);
			}
		};
		dfs(1, 1, 1);
		dfs2(1, 1, 1, INF);
		fill(dis.begin(), dis.end(), INF);
		dfs(1, 1, 0);
		dfs2(1, 1, 0, INF);
		if(ans >= n)
			cout << "-1\n";
		else {
			cout << ans << '\n';
			for(int i = 1; i <= n; i++)
				cout << arr[i] << " \n"[i == n];
		}
	}
}

Subtask #1
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 204 KB Unexpected end of file - int32 expected
2 Incorrect 0 ms 204 KB Unexpected end of file - int32 expected

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 452 KB Output is correct
2 Correct 107 ms 3776 KB Output is correct
3 Correct 70 ms 1100 KB Output is correct

Subtask #3
0.0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 332 KB Unexpected end of file - int32 expected
2 Incorrect 38 ms 6160 KB Unexpected end of file - int32 expected
3 Incorrect 14 ms 2660 KB Unexpected end of file - int32 expected

Subtask #4
0.0 / 45.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 1432 KB Unexpected end of file - int32 expected
2 Incorrect 1 ms 332 KB Unexpected end of file - int32 expected
3 Incorrect 1 ms 332 KB Unexpected end of file - int32 expected
4 Incorrect 0 ms 204 KB Unexpected end of file - int32 expected
5 Incorrect 1 ms 332 KB Unexpected end of file - int32 expected
6 Incorrect 2 ms 588 KB Unexpected end of file - int32 expected
7 Incorrect 1 ms 332 KB Unexpected end of file - int32 expected
8 Incorrect 1 ms 204 KB Unexpected end of file - int32 expected
9 Incorrect 1 ms 332 KB Unexpected end of file - int32 expected

Subtask #5
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 204 KB Unexpected end of file - int32 expected
2 Incorrect 0 ms 204 KB Unexpected end of file - int32 expected
3 Correct 72 ms 452 KB Output is correct
4 Correct 107 ms 3776 KB Output is correct
5 Correct 70 ms 1100 KB Output is correct
6 Incorrect 1 ms 332 KB Unexpected end of file - int32 expected
7 Incorrect 38 ms 6160 KB Unexpected end of file - int32 expected
8 Incorrect 14 ms 2660 KB Unexpected end of file - int32 expected
9 Incorrect 8 ms 1432 KB Unexpected end of file - int32 expected
10 Incorrect 1 ms 332 KB Unexpected end of file - int32 expected
11 Incorrect 1 ms 332 KB Unexpected end of file - int32 expected
12 Incorrect 0 ms 204 KB Unexpected end of file - int32 expected
13 Incorrect 1 ms 332 KB Unexpected end of file - int32 expected
14 Incorrect 2 ms 588 KB Unexpected end of file - int32 expected
15 Incorrect 1 ms 332 KB Unexpected end of file - int32 expected
16 Incorrect 1 ms 204 KB Unexpected end of file - int32 expected
17 Incorrect 1 ms 332 KB Unexpected end of file - int32 expected
18 Incorrect 2 ms 844 KB Unexpected end of file - int32 expected
19 Incorrect 26 ms 6200 KB Unexpected end of file - int32 expected
20 Incorrect 0 ms 204 KB Unexpected end of file - int32 expected
21 Incorrect 263 ms 30216 KB Unexpected end of file - int32 expected
22 Incorrect 1 ms 332 KB Unexpected end of file - int32 expected