Submission #317074

#	Time	Username	Problem	Language	Result	Execution time	Memory
317074		Kevin_Zhang_TW	Balanced Tree (info1cup18_balancedtree)	C++17	23 / 100	933 ms	30200 KiB

balancedtree

#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];
}
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 (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
		exit(1);
}

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

Compilation message (stderr)

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 / 10
• Subtask 2: 13 / 13
• Subtask 3: 0 / 26
• Subtask 4: 0 / 45
• Subtask 5: 0 / 6