oj.uz

Submission #317179

# Submission time Handle Problem Language Result Execution time Memory
317179 2020-10-29T04:59:37 Z Kevin_Zhang_TW Balanced Tree (info1cup18_balancedtree) C++17
13 / 100
 4000 ms 41820 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 (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 < 5;++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 13 ms 12160 KB Output isn't correct
2 Incorrect 18 ms 12160 KB Output isn't correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 13048 KB Output is correct
2 Correct 177 ms 15864 KB Output is correct
3 Correct 126 ms 13944 KB Output is correct

Subtask #3
0.0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 214 ms 12876 KB Output isn't correct
2 Incorrect 791 ms 23616 KB Output isn't correct
3 Incorrect 379 ms 16828 KB Output isn't correct

Subtask #4
0.0 / 45.0

# Verdict Execution time Memory Grader output
1 Incorrect 494 ms 14600 KB Output isn't correct
2 Incorrect 257 ms 12920 KB Output isn't correct
3 Incorrect 283 ms 13048 KB Output isn't correct
4 Incorrect 137 ms 12804 KB Output isn't correct
5 Incorrect 175 ms 12792 KB Output isn't correct
6 Incorrect 345 ms 13560 KB Output isn't correct
7 Correct 255 ms 13048 KB Output is partially correct
8 Incorrect 137 ms 12664 KB Output isn't correct
9 Incorrect 173 ms 12792 KB Output isn't correct

Subtask #5
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 12160 KB Output isn't correct
2 Incorrect 18 ms 12160 KB Output isn't correct
3 Correct 67 ms 13048 KB Output is correct
4 Correct 177 ms 15864 KB Output is correct
5 Correct 126 ms 13944 KB Output is correct
6 Incorrect 214 ms 12876 KB Output isn't correct
7 Incorrect 791 ms 23616 KB Output isn't correct
8 Incorrect 379 ms 16828 KB Output isn't correct
9 Incorrect 494 ms 14600 KB Output isn't correct
10 Incorrect 257 ms 12920 KB Output isn't correct
11 Incorrect 283 ms 13048 KB Output isn't correct
12 Incorrect 137 ms 12804 KB Output isn't correct
13 Incorrect 175 ms 12792 KB Output isn't correct
14 Incorrect 345 ms 13560 KB Output isn't correct
15 Correct 255 ms 13048 KB Output is partially correct
16 Incorrect 137 ms 12664 KB Output isn't correct
17 Incorrect 173 ms 12792 KB Output isn't correct
18 Incorrect 2033 ms 14712 KB Output isn't correct
19 Execution timed out 4016 ms 20300 KB Time limit exceeded
20 Incorrect 662 ms 14200 KB Output isn't correct
21 Execution timed out 4048 ms 41820 KB Time limit exceeded
22 Incorrect 3545 ms 39344 KB Output isn't correct