Submission #959150

#TimeUsernameProblemLanguageResultExecution timeMemory
959150PringPower Plant (JOI20_power)C++17
0 / 100
2 ms4956 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 ans; int DP(int id, int par) { int now = 0, cnt = 0, big = 0; for (auto &i : edge[id]) { if (i == par) continue; int x = DP(i, id); now += x; big = max(big, x); if (x) cnt++; } int cur = 0; if (cnt == 0) cur = (s[id] & 1); else if (cnt == 1) cur = now + (s[id] & 1); else if (s[id] & 1) cur = max({now - 1, big + 1, 1}); else cur = now; ans = max(ans, cur); return cur; } 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; DP(1, 0); 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...