oj.uz

Submission #908600

# Submission time Handle Problem Language Result Execution time Memory
908600 2024-01-16T14:58:30 Z arashMLG Power Plant (JOI20_power) C++17
0 / 100
 4 ms 14936 KB 
#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}):max({1,sum1-1}));}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
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 14936 KB Output is correct
2 Incorrect 4 ms 14936 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 14936 KB Output is correct
2 Incorrect 4 ms 14936 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 14936 KB Output is correct
2 Incorrect 4 ms 14936 KB Output isn't correct
3 Halted 0 ms 0 KB -