oj.uz

답안 #317070

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
317070 2020-10-29T02:33:16 Z Kevin_Zhang_TW Balanced Tree (info1cup18_balancedtree) C++17
10 / 100
 606 ms 30328 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;
	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]]);

	ban[cen] = true;
	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() {
	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();
	else
		exit(1);

	if (cn == 0) {
		cout << cal() << '\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

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

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 146 ms 12152 KB Output is correct
2 Correct 606 ms 12152 KB Output is correct

Subtask #2
0.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 8 ms 12032 KB Execution failed because the return code was nonzero
2 Runtime error 30 ms 13824 KB Execution failed because the return code was nonzero
3 Runtime error 11 ms 12416 KB Execution failed because the return code was nonzero

Subtask #3
0.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 8 ms 12032 KB Execution failed because the return code was nonzero
2 Runtime error 51 ms 15736 KB Execution failed because the return code was nonzero
3 Runtime error 21 ms 13440 KB Execution failed because the return code was nonzero

Subtask #4
0.0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 16 ms 12800 KB Execution failed because the return code was nonzero
2 Runtime error 8 ms 12160 KB Execution failed because the return code was nonzero
3 Runtime error 8 ms 12160 KB Execution failed because the return code was nonzero
4 Runtime error 8 ms 12032 KB Execution failed because the return code was nonzero
5 Runtime error 8 ms 12288 KB Execution failed because the return code was nonzero
6 Runtime error 10 ms 12288 KB Execution failed because the return code was nonzero
7 Runtime error 8 ms 12160 KB Execution failed because the return code was nonzero
8 Runtime error 8 ms 12032 KB Execution failed because the return code was nonzero
9 Runtime error 8 ms 12160 KB Execution failed because the return code was nonzero

Subtask #5
0.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 146 ms 12152 KB Output is correct
2 Correct 606 ms 12152 KB Output is correct
3 Runtime error 8 ms 12032 KB Execution failed because the return code was nonzero
4 Runtime error 30 ms 13824 KB Execution failed because the return code was nonzero
5 Runtime error 11 ms 12416 KB Execution failed because the return code was nonzero
6 Runtime error 8 ms 12032 KB Execution failed because the return code was nonzero
7 Runtime error 51 ms 15736 KB Execution failed because the return code was nonzero
8 Runtime error 21 ms 13440 KB Execution failed because the return code was nonzero
9 Runtime error 16 ms 12800 KB Execution failed because the return code was nonzero
10 Runtime error 8 ms 12160 KB Execution failed because the return code was nonzero
11 Runtime error 8 ms 12160 KB Execution failed because the return code was nonzero
12 Runtime error 8 ms 12032 KB Execution failed because the return code was nonzero
13 Runtime error 8 ms 12288 KB Execution failed because the return code was nonzero
14 Runtime error 10 ms 12288 KB Execution failed because the return code was nonzero
15 Runtime error 8 ms 12160 KB Execution failed because the return code was nonzero
16 Runtime error 8 ms 12032 KB Execution failed because the return code was nonzero
17 Runtime error 8 ms 12160 KB Execution failed because the return code was nonzero
18 Runtime error 11 ms 12416 KB Execution failed because the return code was nonzero
19 Runtime error 53 ms 15608 KB Execution failed because the return code was nonzero
20 Runtime error 8 ms 12032 KB Execution failed because the return code was nonzero
21 Runtime error 315 ms 30328 KB Execution failed because the return code was nonzero
22 Runtime error 8 ms 12160 KB Execution failed because the return code was nonzero