Submission #631895

#	Time	Username	Problem	Language	Result	Execution time	Memory
631895		radal	Power Plant (JOI20_power)	C++17	100 / 100	165 ms	29576 KiB

power

#include <bits/stdc++.h>
#define rep(i,l,r) for (int i = l; i < r; i++)
#define pb push_back

using namespace std;

constexpr int N = 2e5+10;

int dp[N][2],n;
vector<int> adj[N];
string s;
void dfs(int v,int p){
    for (int u : adj[v]){
        if (u != p){
            dfs(u,v);
        }
    }
    if (s[v-1] == '0'){
        int su = 0;
        for (int u : adj[v]){
            if (u == p) continue;
            su += dp[u][1];
            dp[v][0] = max(dp[v][0],dp[u][0]);
        }
        dp[v][0] = max(dp[v][0],su);
        dp[v][1] = su;
        return;
    }
    dp[v][0] = dp[v][1] = 1;
    int su = 0;
    for (int u : adj[v]){
        if (u == p) continue;
        dp[v][0] = max({dp[v][0],dp[u][0],1+dp[u][1]});
        su += dp[u][1];
    }
    dp[v][0] = max(dp[v][0],su-1);
    dp[v][1] = max(dp[v][1],su-1);
}

int main(){
    ios_base :: sync_with_stdio(0); cin.tie(0);
    cin >> n;
    rep(i,1,n){
        int u,v;
        cin >> u >> v;
        adj[u].pb(v);
        adj[v].pb(u);
    }
    cin >> s;
    dfs(1,0);
    cout << dp[1][0];
}

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