Submission #1141039

#TimeUsernameProblemLanguageResultExecution timeMemory
1141039the_coding_poohPower Plant (JOI20_power)C++20
100 / 100
219 ms26940 KiB
#include <bits/stdc++.h>
#define uwu return 0;

using namespace std;

const int SIZE = 2e5 + 5;

vector <int> graph[SIZE];

int dp[2][SIZE];

bool is_power[SIZE];

void dfs(int nd, int rt){
    for(auto i:graph[nd]){
        if(i == rt)
            continue;
        dfs(i, nd);
        if(is_power[nd]){
            dp[0][nd] = max({dp[0][nd], dp[0][i], dp[1][i] + 1});
            dp[1][nd] += max({0, dp[1][i]});
        }
        else{
            dp[0][nd] = max({dp[0][nd], dp[0][i]});
            dp[1][nd] += max({0, dp[1][i]});
        }
    }
    if(is_power[nd]){
        dp[0][nd] = max({dp[0][nd], dp[1][nd] - 1, 1});
        dp[1][nd] = max({dp[1][nd] - 1 , 1});
    }
    else{
        dp[0][nd] = max({dp[0][nd], dp[1][nd]});
    }
    return;
}

int main(){
    int N;
    cin >> N;
    for (int a, b, i = 1; i < N; i++){
        cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    for (int i = 1; i <= N; i++){
        char c;
        cin >> c;
        is_power[i] = (c == '1');
    }
    dfs(1, 0);
    cout << dp[0][1] << '\n';
    uwu
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...