Submission #1146150

#	Time	Username	Problem	Language	Result	Execution time	Memory
1146150		fatman87878	Power Plant (JOI20_power)	C++20	100 / 100	127 ms	28864 KiB

power

#include<bits/stdc++.h>
using namespace std;
#define IOS cin.tie(nullptr)->sync_with_stdio(0),cin.exceptions(cin.failbit);
#define lb(x) (x)&-(x)
#define all(x) (x).begin(),(x).end()
#define ll long long

constexpr int maxN=2e5+5;

int n,dp[maxN],ans;

string s;

vector<int> adj[maxN];

void dfs(int now,int last){
    dp[now] = -(s[now]=='1');
    int mx = 0;
    for(int i:adj[now])if(i!=last){
        dfs(i,now);
        dp[now]+=dp[i];
        mx = max(mx,dp[i]);
    }
    dp[now] = max((int)(s[now]=='1'),dp[now]);
    ans = max({ans,dp[now],mx+(s[now]=='1')});
    return;
}

int main(){
    IOS
    cin>>n;
    for(int a,b,i = 1;i<n;i++)cin>>a>>b,adj[adj[a].emplace_back(b)].emplace_back(a);
    cin>>s;
    s=' '+s;
    dfs(1,1);
    cout<<ans<<'\n';
}

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