Submission #423356

#	Time	Username	Problem	Language	Result	Execution time	Memory
423356		DanerZein	Power Plant (JOI20_power)	C++14	100 / 100	299 ms	28768 KiB

power

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
const int MAX_N=2e5+10;
vector<vi> G;
string x;
int dp[MAX_N],pa[MAX_N];
int ans=0;
int dfs(int u,int p){
  int ma=0;
  int s=0;
  bool hj=0;
  for(auto &v:G[u]){
    if(v!=p){
      hj=1;
      int aux=dfs(v,u);
      ma=max(ma,aux);
      s+=aux;
    }
  }
  int mi=0;
  if(x[u]=='1'){
    ma++; s--;
    mi=1;
  }
  ans=max(ans,ma);
  return dp[u]=max(s,mi);
}
int main(){
  int n;
  cin>>n;
  G.resize(n+1);
  for(int i=0;i<n-1;i++){
    int a,b; cin>>a>>b;
    a--; b--;
    G[a].push_back(b);
    G[b].push_back(a);
  }
  cin>>x;
  cout<<max(ans,dfs(0,-1))<<endl;
 
}

Compilation message (stderr)

power.cpp: In function 'int dfs(int, int)':
power.cpp:13:8: warning: variable 'hj' set but not used [-Wunused-but-set-variable]
   13 |   bool hj=0;
      |        ^~

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