Submission #320598

#	Time	Username	Problem	Language	Result	Execution time	Memory
320598		GioChkhaidze	Power Plant (JOI20_power)	C++14	100 / 100	232 ms	26148 KiB

power

#include <bits/stdc++.h>

#define pb push_back

using namespace std;
 
const int N=2e5+5;

string s; 
int n,a,b,dp[N];
vector < int > v[N];

void dfs(int x,int p) {
  int t=(s[x-1]=='1'),res=0;
  dp[x]=t;
  for (int i=0; i<v[x].size(); i++) {
    int to=v[x][i];
    if (to==p) continue;
    dfs(to,x);
    res+=dp[to];
  }
  res-=t;
  dp[x]=max(res,dp[x]);
}

int ans;
void Dfs(int x,int p,int res) {
  int t=(s[x-1]=='1'),S=res-t;
  
  for (int i=0; i<v[x].size(); i++) {
    int to=v[x][i];
    if (to==p) continue;
    S+=dp[to];
  }

  ans=max(ans,S);
  for (int i=0; i<v[x].size(); i++) {
    int to=v[x][i];
    if (to==p) continue;
    Dfs(to,x,max(t,S-dp[to]));
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL),cout.tie(NULL);
 
  cin>>n;
  for (int i=1; i<n; i++) {
    cin>>a>>b;
    v[a].pb(b);
    v[b].pb(a);
  }
  
  cin>>s;
  
  int cnt=0;
  for (int i=0; i<s.size(); i++) 
    if (s[i]=='1') cnt++;
    
  ans=min(2,cnt);
  
  dfs(1,1);
  Dfs(1,1,0);
  
  cout<<ans<<"\n";
}

Compilation message (stderr)

power.cpp: In function 'void dfs(int, int)':
power.cpp:16:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |   for (int i=0; i<v[x].size(); i++) {
      |                 ~^~~~~~~~~~~~
power.cpp: In function 'void Dfs(int, int, int)':
power.cpp:30:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |   for (int i=0; i<v[x].size(); i++) {
      |                 ~^~~~~~~~~~~~
power.cpp:37:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |   for (int i=0; i<v[x].size(); i++) {
      |                 ~^~~~~~~~~~~~
power.cpp: In function 'int main()':
power.cpp:58:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |   for (int i=0; i<s.size(); i++)
      |                 ~^~~~~~~~~

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