oj.uz

Submission #317181

# Submission time Handle Problem Language Result Execution time Memory
317181 2020-10-29T05:02:30 Z Kevin_Zhang_TW Balanced Tree (info1cup18_balancedtree) C++17
23 / 100
 4000 ms 40552 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;

	ban[cen] = true;

	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]]);

	for (int u : edge[cen])
		dfs_solve(u);
}
	
void cal_init() {
	for (int i = 1;i <= n;++i) {
		dis[i] = inf;
		ban[i] = false;
	}
}
int cal() {
	cal_init();
	dfs_solve(1);
	return *max_element(dis+1, dis+n+1);
}
int bfs(int s) {
	queue<pair<int,int>> q;
	vector<bool> vis(n+1);
	q.emplace(s, 0);
	vis[s] = true;
	while (q.size()) {
		auto [x, len] = q.front(); q.pop();
		if (x != s && c[x] == c[s])
			return len;
		for (int u : edge[x]) if (!vis[u])
			q.emplace(u, len+1), vis[u] = true;
	}
	return inf;
}
int brute_cal() {
	cal_init();
	int res = 0;
	for (int i = 1;i <= n;++i) 
		res = max(res, bfs(i));
	return res;
}
void brute_solve() {
	int res = inf, p;
	for (int s = 0;s < 1<<n;++s) {
		bool ok = true;
		for (int i = 0;i < n;++i)
			if (c[i+1] != -1 && c[i+1] != (s>>i&1)) 
				ok = false;
		if (!ok) continue;
		DE(s);
		vector<int> oldc(c, c+n+1);
		for (int i = 0;i < n;++i)
			c[i+1] = s>>i&1;
		int val = brute_cal();
		chmin(res, val);
		if (res == val) p = s;
		copy(AI(oldc), c);
		
	}
	if (res > n) {
		assert(false);
		return cout << -1 << '\n', void();
	}

	cout << res << '\n';
	for (int i = 0;i < n;++i)
		cout << (p>>i&1) << " \n"[i+1==n];
}
random_device rd;
mt19937 gen(rd());
int ra(int l, int r) {
	return uniform_int_distribution<int> (l, r)(gen);
}
pair<int, vector<int>> holan() {
	vector<int> oldc(c, c+n+1);
	for (int i = 1;i <= n;++i)
		if (c[i] == -1) c[i] = ra(0, 1);
	pair<int, vector<int>> res = {cal(), vector<int>(c, c+n+1)};
	copy(AI(oldc), c);
	return res;
}
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 ((c0==1) + (c1==1) > cn)
		return cout << -1 << '\n', void();

	if (!c0) {
		for (int i = 1;i <= n;++i)
			c[i] = 1;
		cn = 0;
	}
	if (!c1) {
		for (int i = 1;i <= n;++i)
			c[i] = 0;
		cn = 0;
	}

	if (n <= 17)
		return brute_solve(), void();

	if (cn == 0) {
		int val = cal();
		if (val > n)
			return cout << -1 << '\n', void();
		cout << val << '\n';
		for (int i = 1;i <= n;++i)
			cout << c[i] << " \n"[i==n];
	}
	else {
		pair<int, vector<int>> ans = {inf, {}};
		for (int x = 0;x < 50;++x)
			ans = min(ans, holan());

		auto [val, c] = ans;
		if (val > n)
			return cout << -1 << '\n', void();
		cout << val << '\n';
		for (int i = 1;i <= n;++i)
			cout << c[i] << " \n"[i==n];
	}
}

int32_t main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	int T;
	cin >> T;
	while (T--)
		solve();
}

Compilation message

balancedtree.cpp: In function 'void brute_solve()':
balancedtree.cpp:14:17: warning: statement has no effect [-Wunused-value]
   14 | #define DE(...) 0
      |                 ^
balancedtree.cpp:116:3: note: in expansion of macro 'DE'
  116 |   DE(s);
      |   ^~
balancedtree.cpp:133:13: warning: 'p' may be used uninitialized in this function [-Wmaybe-uninitialized]
  133 |   cout << (p>>i&1) << " \n"[i+1==n];
      |            ~^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 225 ms 12160 KB Output is correct
2 Correct 945 ms 12180 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 12412 KB Output is correct
2 Correct 185 ms 14584 KB Output is correct
3 Correct 117 ms 12792 KB Output is correct

Subtask #3
0.0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 1797 ms 12528 KB Output isn't correct
2 Execution timed out 4046 ms 22392 KB Time limit exceeded
3 Incorrect 3372 ms 16512 KB Output isn't correct

Subtask #4
0.0 / 45.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4010 ms 13804 KB Time limit exceeded
2 Incorrect 2039 ms 12552 KB Output isn't correct
3 Incorrect 2358 ms 12756 KB Output isn't correct
4 Correct 775 ms 12408 KB Output is partially correct
5 Incorrect 1307 ms 12664 KB Output isn't correct
6 Incorrect 2895 ms 13048 KB Output isn't correct
7 Correct 2019 ms 12664 KB Output is partially correct
8 Incorrect 780 ms 12536 KB Output isn't correct
9 Incorrect 1282 ms 12664 KB Output isn't correct

Subtask #5
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 225 ms 12160 KB Output is correct
2 Correct 945 ms 12180 KB Output is correct
3 Correct 63 ms 12412 KB Output is correct
4 Correct 185 ms 14584 KB Output is correct
5 Correct 117 ms 12792 KB Output is correct
6 Incorrect 1797 ms 12528 KB Output isn't correct
7 Execution timed out 4046 ms 22392 KB Time limit exceeded
8 Incorrect 3372 ms 16512 KB Output isn't correct
9 Execution timed out 4010 ms 13804 KB Time limit exceeded
10 Incorrect 2039 ms 12552 KB Output isn't correct
11 Incorrect 2358 ms 12756 KB Output isn't correct
12 Correct 775 ms 12408 KB Output is partially correct
13 Incorrect 1307 ms 12664 KB Output isn't correct
14 Incorrect 2895 ms 13048 KB Output isn't correct
15 Correct 2019 ms 12664 KB Output is partially correct
16 Incorrect 780 ms 12536 KB Output isn't correct
17 Incorrect 1282 ms 12664 KB Output isn't correct
18 Execution timed out 4043 ms 13044 KB Time limit exceeded
19 Execution timed out 4034 ms 18124 KB Time limit exceeded
20 Incorrect 3887 ms 13428 KB Output isn't correct
21 Execution timed out 4054 ms 40552 KB Time limit exceeded
22 Execution timed out 4019 ms 35004 KB Time limit exceeded