Submission #317068

#TimeUsernameProblemLanguageResultExecution timeMemory
317068Kevin_Zhang_TWBalanced Tree (info1cup18_balancedtree)C++17
0 / 100
607 ms30200 KiB
#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); } 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 (min(c0, c1) == 1 && cn == 0) return cout << -1 << '\n', void(); if (n <= 17) return brute_solve(), void(); 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 (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:113:3: note: in expansion of macro 'DE'
  113 |   DE(s);
      |   ^~
balancedtree.cpp:125:13: warning: 'p' may be used uninitialized in this function [-Wmaybe-uninitialized]
  125 |   cout << (p>>i&1) << " \n"[i+1==n];
      |            ~^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...