Submission #1120082

#	Time	Username	Problem	Language	Result	Execution time	Memory
1120082		irmuun	Power Plant (JOI20_power)	C++17	47 / 100	1549 ms	16016 KiB

power

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()

const int N=2e5+5;

int n,ans=0;
vector<int>g[N];
string s;
int dp[N],e[N];

void dfs(int x,int p){
    e[x]=(s[x]=='1'?1:0);
    dp[x]=0;
    for(int y:g[x]){
        if(y!=p){
            dfs(y,x);
            dp[x]+=dp[y];
        }
    }
    dp[x]=max(dp[x]-e[x],e[x]);
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin>>n;
    for(int i=1;i<n;i++){
        int a,b;
        cin>>a>>b;
        a--,b--;
        g[a].pb(b);
        g[b].pb(a);
    }
    cin>>s;
    for(int i=0;i<n;i++){
        if(s[i]=='1'){
            dfs(i,i);
            for(int j:g[i]){
                ans=max(ans,dp[j]+1);
            }
            ans=max(ans,dp[i]);
        }
    }
    cout<<ans;
}

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