Submission #309036

#TimeUsernameProblemLanguageResultExecution timeMemory
309036nhdtxdyPower Plant (JOI20_power)C++17
100 / 100
212 ms29044 KiB
//#pragma GCC optimize("Ofast") //#pragma GCC optimization("unroll-loops, no-stack-protector") //#pragma GCC target("avx,avx2,fma") #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> #define Snape int main() #define lumos ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); #define nox return 0 #define ll long long #define pb push_back #define Size(v) (int)v.size() #define FOR(i, x, y) for(int i = x; i <= y; ++i) #define trav(a, x) for(auto &a : x) using namespace std; using namespace __gnu_pbds; /* "After all this time?" "Always" */ const int nax = 2e5+5; int n, dp[nax]; vector<int> g[nax]; string s; int ans=0; void dfs(int v, int p=0) { trav(c, g[v]) { if (c==p) continue; dfs(c, v); } int val = (s[v]=='1'); dp[v]=max(dp[v],val); int sum=0; trav(c, g[v]) { if (c==p) continue; sum+=dp[c]; } dp[v]=max(dp[v],sum-val); ans=max(ans,dp[v]); trav(c, g[v]) { if (c==p) continue; ans=max(ans,dp[c]+val); } } //void calc(int v, int p=0) { // trav(c, g[v]) { // if (c==p) continue; // calc(c, v); // } // int val = (s[v]=='1'); // if (val==0) { // int sum=0; // trav(c, g[v]) { // if (c==p) continue; // sum+=dp[c]; // } // ans=max(ans,sum); // } // else { // int sum=0; // trav(c, g[v]) { // if (c == p) continue; // ans=max(ans,dp[c]+1); // sum+=dp[c]; // } // ans=max(ans,sum-1); // } //} int main() { lumos; cin >> n; FOR (i,1,n-1) { int a,b; cin>>a>>b; g[a].pb(b); g[b].pb(a); } cin >> s; s = ' ' + s; dfs(1); // calc(1); cout<<ans; nox; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...