Submission #825838

#	Time	Username	Problem	Language	Result	Execution time	Memory
825838		Hakiers	Power Plant (JOI20_power)	C++17	100 / 100	97 ms	29884 KiB

power

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
const int MAXN = 2e5 + 7;
vector<int> G[MAXN];
bool generator[MAXN];
int dp[MAXN][2]; 
// dp[v][1] idziemy w gore, dp[v][0] najlepszy wynik dla poddrzewa
int n;

void dfs(int v, int p){

    int sumson = 0;


    for(auto u : G[v]){
        if(u == p) continue;
        dfs(u, v);
        sumson += dp[u][1];
        dp[v][0] = max(dp[v][0], dp[u][0]); // wyniki dla poddrzew
        if(generator[v]) dp[v][0] = max(dp[v][0], dp[u][1] + 1); // jezeli jakas sciezka konczy sie w nas 
    }

     // jezeli laczymy wszystkie poddrzewa i przechodzi przez nas 
    if(generator[v]) dp[v][0] = max({dp[v][0], sumson - 1, 1});
    else dp[v][0] = max(dp[v][0], sumson);


    if(generator[v]) 
        dp[v][1] = max(sumson - 1, 1);
    else 
        dp[v][1] = sumson;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for(int i = 1; i < n; i++){
        int a, b;
        cin >> a >> b;
        G[a].push_back({b});
        G[b].push_back({a});
    }

    string s;
    cin >> s;
    s = "#" + s;
    for(int i = 1; i <= n; i++)
        generator[i] = (s[i] - '0');

    dfs(1, 1);

    cout << dp[1][0] << endl;
    
}

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