Submission #959136

#TimeUsernameProblemLanguageResultExecution timeMemory
959136PringPower Plant (JOI20_power)C++17
0 / 100
2 ms5724 KiB
#include <bits/stdc++.h> using namespace std; #ifdef MIKU string dbmc = "\033[1;38;2;57;197;187m", dbrs = "\033[0m"; #define debug(x...) cout << dbmc << "[" << #x << "]: ", dout(x) void dout() { cout << dbrs << endl; } template <typename T, typename ...U> void dout(T t, U ...u) { cout << t << (sizeof...(u) ? ", " : ""); dout(u...); } #else #define debug(...) 39 #endif #define fs first #define sc second #define mp make_pair #define FOR(i, j, k) for (int i = j, Z = k; i < Z; i++) typedef pair<int, int> pii; const int MXN = 200005; int n; vector<int> edge[MXN]; string s; int sz[MXN], ans; bitset<MXN> ban; void GET_SZ(int id, int par) { sz[id] = 1; for (auto &i : edge[id]) { if (i == par) continue; if (ban[i]) continue; GET_SZ(i, id); sz[id] += sz[i]; } } int GET_CD(int id, int par, int S) { for (auto &i : edge[id]) { if (i == par) continue; if (ban[i]) continue; if (sz[i] > S / 2) return GET_CD(i, id, S); } return id; } int DP(int id, int par) { int ans = ((s[id] & 1) ? -1 : 0); for (auto &i : edge[id]) { if (i == par) continue; if (ban[i]) continue; ans += DP(i, id); } if (s[id] & 1) ans = max(ans, 1); return ans; } int calc(int id) { int now = 0, cnt = 0; for (auto &i : edge[id]) { if (ban[i]) continue; int x = DP(i, id); now += x; if (x) cnt++; } if (cnt == 0) return (s[id] & 1); if (cnt == 1) return now + (s[id] & 1); if (s[id] & 1) return max(1, now - 1); return now; } void CD(int id) { GET_SZ(id, 0); int ct = GET_CD(id, 0, sz[id]); ans = max(ans, calc(ct)); ban[ct] = true; for (auto &i : edge[ct]) { if (ban[i]) continue; CD(i); } } void miku() { int x, y; cin >> n; FOR(i, 1, n) { cin >> x >> y; edge[x].push_back(y); edge[y].push_back(x); } cin >> s; s = " " + s; CD(1); cout << ans << '\n'; } int32_t main() { cin.tie(0) -> sync_with_stdio(false); cin.exceptions(cin.failbit); miku(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...