제출 #1141039

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1141039		the_coding_pooh	Power Plant (JOI20_power)	C++20	100 / 100	219 ms	26940 KiB

power

#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
}

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