Submission #532239

#TimeUsernameProblemLanguageResultExecution timeMemory
532239nhdtxdyPower Plant (JOI20_power)C++17
100 / 100
190 ms28784 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'); if (val) dp[v] = 1; int sum=0; trav(c, g[v]) { if (c==p) continue; sum+=dp[c]; } if (val) { dp[v] = max(dp[v], sum - val); } else dp[v] = max(dp[v], sum); } void calc(int v, int p=0) { ans=max(ans,dp[v]); trav(c, g[v]) { if (c==p) continue; calc(c, v); } int val = (s[v]=='1'); if (val) { trav(c, g[v]) { if (c == p) continue; ans=max(ans,dp[c]+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...