oj.uz

Submission #317180

# Submission time Handle Problem Language Result Execution time Memory
317180 2020-10-29T05:01:15 Z Kevin_Zhang_TW Balanced Tree (info1cup18_balancedtree) C++17
13 / 100
 4000 ms 40476 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)
		brute_solve();

	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 < 10;++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
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 233 ms 12280 KB Restrictions are not satisfied
2 Incorrect 962 ms 12408 KB Restrictions are not satisfied

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 12280 KB Output is correct
2 Correct 191 ms 14712 KB Output is correct
3 Correct 122 ms 12920 KB Output is correct

Subtask #3
0.0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 369 ms 12384 KB Output isn't correct
2 Incorrect 1445 ms 22440 KB Output isn't correct
3 Incorrect 693 ms 16356 KB Output isn't correct

Subtask #4
0.0 / 45.0

# Verdict Execution time Memory Grader output
1 Incorrect 907 ms 13856 KB Output isn't correct
2 Incorrect 444 ms 12536 KB Output isn't correct
3 Incorrect 509 ms 12668 KB Output isn't correct
4 Incorrect 215 ms 12280 KB Output isn't correct
5 Incorrect 302 ms 12536 KB Output isn't correct
6 Incorrect 630 ms 12664 KB Output isn't correct
7 Correct 444 ms 12392 KB Output is partially correct
8 Incorrect 225 ms 12488 KB Output isn't correct
9 Incorrect 297 ms 12408 KB Output isn't correct

Subtask #5
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 233 ms 12280 KB Restrictions are not satisfied
2 Incorrect 962 ms 12408 KB Restrictions are not satisfied
3 Correct 63 ms 12280 KB Output is correct
4 Correct 191 ms 14712 KB Output is correct
5 Correct 122 ms 12920 KB Output is correct
6 Incorrect 369 ms 12384 KB Output isn't correct
7 Incorrect 1445 ms 22440 KB Output isn't correct
8 Incorrect 693 ms 16356 KB Output isn't correct
9 Incorrect 907 ms 13856 KB Output isn't correct
10 Incorrect 444 ms 12536 KB Output isn't correct
11 Incorrect 509 ms 12668 KB Output isn't correct
12 Incorrect 215 ms 12280 KB Output isn't correct
13 Incorrect 302 ms 12536 KB Output isn't correct
14 Incorrect 630 ms 12664 KB Output isn't correct
15 Correct 444 ms 12392 KB Output is partially correct
16 Incorrect 225 ms 12488 KB Output isn't correct
17 Incorrect 297 ms 12408 KB Output isn't correct
18 Incorrect 3780 ms 14200 KB Output isn't correct
19 Execution timed out 4018 ms 18556 KB Time limit exceeded
20 Incorrect 1067 ms 13396 KB Output isn't correct
21 Execution timed out 4035 ms 40476 KB Time limit exceeded
22 Execution timed out 4085 ms 37444 KB Time limit exceeded