Submission #1244489

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244489		inkvizytor	Power Plant (JOI20_power)	C++20	100 / 100	230 ms	40072 KiB

power

#include <bits/stdc++.h>
using namespace std;

#define ll long long

int sc = 0;

void dfs (int v, vector<vector<int>> &g, vector<bool> &odw, vector<int> &dp, vector<bool> &c) {
    odw[v] = 1;
    vector<int> x;
    int s = 0;
    for (int u : g[v]) {
        if (!odw[u]) {
            dfs(u, g, odw, dp, c);
            x.push_back(dp[u]);
            s += dp[u];
        }
    }
    if (!c[v]) {
        dp[v] = s;
    }
    else {
        if (x.empty()) {
            dp[v] = 1;
            sc = max(sc, 1);
            return;
        }
        sort(x.begin(), x.end(), greater<int>());
        sc = max(sc, x[0]+1);
        dp[v] = max(1, s-1);
    }
    sc = max(sc, dp[v]);
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    vector<vector<int>> g (n+1);
    for (int i = 0; i < n-1; i++) {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    string s;
    cin >> s;
    vector<bool> c (n+1, 0);
    for (int i = 0; i < n; i++) {
        c[i+1] = (s[i]=='1');
    }
    vector<bool> odw (n+1, 0);
    vector<int> dp (n+1, 0);
    dfs(1, g, odw, dp, c);
    cout << sc << '\n';
}

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