Submission #1031125

#TimeUsernameProblemLanguageResultExecution timeMemory
1031125vjudge1Power Plant (JOI20_power)C++17
100 / 100
70 ms31632 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define ld long double #define pii pair<int, int> #define pll pair<ll, ll> #define pld pair<ld, ld> #define pb push_back #define fi first #define se second #define debug(x) cout << #x << " => " << x << endl #define all(x) x.begin(),x.end() vector<int> adj[200010]; string s; int ans; int dp[200010]; void dfs(int u,int p) { int sum=0,mx=0; for(auto i : adj[u]) { if(i!=p) { dfs(i,u); sum+=dp[i]; mx=max(mx,dp[i]); } } if(s[u-1]=='0') dp[u]=sum; else { dp[u]=max(1,sum-1); ans=max(ans,mx+1); } ans=max(ans,dp[u]); } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int n;cin>>n; for(int i=1;i<n;i++) { int u,v;cin>>u>>v; adj[u].pb(v); adj[v].pb(u); } cin>>s; dfs(1,-1); cout<<ans; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...