Submission #908602

#	Time	Username	Problem	Language	Result	Execution time	Memory
908602		arashMLG	Power Plant (JOI20_power)	C++17	100 / 100	281 ms	39760 KiB

power

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
const int N=5e5+23;int n,dp[N][2],is[N];vector<int> G[N];void dfs(int v,int p=-1) {int sum0=0,sum1=0,mx1=0,mx0=0;for(int u:G[v]) if(u!=p) {dfs(u,v);sum0+=dp[u][0];sum1+=dp[u][1];mx1=max(mx1,dp[u][1]);mx0=max(mx0,dp[u][0]);}dp[v][0]=(is[v]?max({mx0,sum1-1,1+mx1}):max({mx0,sum1}));dp[v][1]=(is[v]?max({1,sum1-1}):sum1);}int main(){cin>>n;for(int i=1; i<n ; i++) {int v,u;cin>>v>>u;G[v].pb(u);G[u].pb(v);}for(int i=1;i<=n;i++) {char c; cin>>c;is[i]=(c=='1');}dfs(1);cout<<dp[1][0]<<'\n';}

• Subtask 1: 6 / 6
• Subtask 2: 41 / 41
• Subtask 3: 53 / 53