Submission #402352

#	Time	Username	Problem	Language	Result	Execution time	Memory
402352		wildturtle	Power Plant (JOI20_power)	C++14	100 / 100	321 ms	32788 KiB

power

#include<bits/stdc++.h>
#define ll long long
#define f first
#define sc second
#define pb push_back
using namespace std;
ll a,b,c,d,i,e,f,g,n,m,k,l,ans,A[500005],B[500005];
vector <ll> v[500005];
string s;
void dfs(ll x,ll y) {
    for(ll i=0;i<v[x].size();i++) {
        if(v[x][i]==y) continue;
        dfs(v[x][i],x);
        A[x]+=A[v[x][i]];
        B[x]+=B[v[x][i]];
    }
    if(s[x-1]=='1') { A[x]=max(A[x]-1, (ll)1 ); B[x]++; }
    
}
int main() {
    cin>>n;
    for(ll i=1;i<n;i++) {
        cin>>a>>b;
        v[a].pb(b);
        v[b].pb(a);
    }
    cin>>s;
    a=0;
    for(ll i=0;i<n;i++) {
        if(s[i]=='1') a++;
    }
    dfs(1,0);
    for(ll x=1;x<=n;x++) {
        //cout<<x<<" "<<A[x]<<" "<<B[x]<<" "<<a<<endl;
        if(B[x]<a) ans=max(ans,A[x]+1);
        else ans=max(ans,A[x]);
    }
    cout<<ans;
}

Compilation message (stderr)

power.cpp: In function 'void dfs(long long int, long long int)':
power.cpp:11:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 |     for(ll i=0;i<v[x].size();i++) {
      |                ~^~~~~~~~~~~~

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