Submission #1165877

#	Time	Username	Problem	Language	Result	Execution time	Memory
1165877		AlgorithmWarrior	Power Plant (JOI20_power)	C++20	100 / 100	182 ms	29268 KiB

power

#include <bits/stdc++.h>

using namespace std;

int const MAX=2e5+5;
int n;
vector<int>tree[MAX];
int special[MAX];
int ans;
int dp[MAX];

void read(){
    cin>>n;
    int i;
    for(i=1;i<n;++i){
        int u,v;
        cin>>u>>v;
        tree[u].push_back(v);
        tree[v].push_back(u);
    }
    for(i=1;i<=n;++i){
        char ch;
        cin>>ch;
        special[i]=ch-'0';
    }
}

void maxself(int& x,int val){
    if(x<val)
        x=val;
}

void dfs(int nod,int tata){
    int sum=0,mxm=0;
    for(auto fiu : tree[nod])
        if(fiu!=tata){
            dfs(fiu,nod);
            sum+=dp[fiu];
            maxself(mxm,dp[fiu]);
        }
    if(special[nod]){
        maxself(ans,1+mxm);
        dp[nod]=max(sum-1,1);
    }
    else
        dp[nod]=sum;
    maxself(ans,dp[nod]);
}

int main()
{
    read();
    dfs(1,0);
    cout<<ans;
    return 0;
}

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