Submission #424317

#TimeUsernameProblemLanguageResultExecution timeMemory
424317abdzagPower Plant (JOI20_power)C++17
100 / 100
434 ms124564 KiB
#include<bits/stdc++.h> #include<unordered_map> #define rep(i,a,b) for(int i=int(a);i<int(b);i++) #define rrep(i,a,b) for(int i=int(a);i>int(b);i--) #define trav(a,v) for(auto& a: v) #define sz(v) v.size() #define all(v) v.begin(),v.end() #define vi vector<int> typedef long long ll; typedef long double ld; typedef unsigned long long ull; const long long inf = 1e15; using namespace std; vector<vector<ll>> dp(1e6,vector<ll>(2,-inf)); vector<ll> parents(1e6); vector<vector<ll>> children(1e6); string s; ll solve(ll cur,bool lit) { if (children[cur].size() == 0) { return s[cur-1] == '1'; } if (dp[cur][lit] != -inf)return dp[cur][lit]; ll ans1=-inf; ll ans2=-inf; ll ans3 = 0; ll ans4 = 0; trav(a, children[cur]) { ans1 = max(ans1, solve(a,lit)); } trav(a, children[cur]) { ans2 = max(ans2, solve(a, 1)); } ll one = 1; ll zero = 0; if (s[cur - 1] == '1') { if (lit)ans2 -= 1, ans1 -= 1; else ans2++; ans2 = max(one, ans2); } ans1 = max(zero, ans1); trav(a, children[cur]) { ans3 += solve(a, 1); } trav(a, children[cur]) { ans4 += solve(a, 1); } if (s[cur - 1] == '1') { ans3--; ans4--; } //cout << "cur: " << cur << endl; //cout << ans1 << " "<<ans2<<" "<<ans3<<" "<<ans4<<endl; return dp[cur][lit] = max(max(ans1, ans2),max(ans3,ans4)); } int main() { cin.sync_with_stdio(false); ll n; cin >> n; vector<vector<ll>> g(n + 1); rep(i, 0, n-1) { ll a, b; cin >> a >> b; g[a].push_back(b); g[b].push_back(a); } cin >> s; if (n == 1) { cout << (s == "1" ? 1 : 0)<<endl; return 0; } else if (n == 2) { ll ans = 0; trav(a, s)ans += a == '1'; cout << ans << endl; return 0; } queue<ll> q; vector<bool> isLeaf(n+1); rep(i, 1, n + 1)if (g[i].size() == 1)isLeaf[i]=1; ll root = -1; rep(i, 1, n + 1)if (!isLeaf[i])root = i; q.push(root); vector<bool> visited(n + 1); visited[root] = 1; while (!q.empty()) { ll cur = q.front(); q.pop(); trav(a, g[cur]) { if (!visited[a]) { parents[a] = cur; children[cur].push_back(a); visited[a] = 1; q.push(a); } } } rep(i, 1, n + 1) { if (isLeaf[i]) { q.push(i); } } parents[root] = -1; cout << solve(root,0); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...