Submission #349008

#	Time	Username	Problem	Language	Result	Execution time	Memory
349008		apostoldaniel854	Power Plant (JOI20_power)	C++14	100 / 100	228 ms	31696 KiB

power

#include <bits/stdc++.h>

using namespace std;

#define pb push_back

const int MAX_N = 2e5;
int dp[1 + MAX_N];
vector <int> gr[1 + MAX_N];

int dfs_calc (int node, int par, string &gen) {
    int mx = 0;
    int is_gen = gen[node] - '0';
    int ans = 0;
    for (int son : gr[node])
        if (son != par) {
            ans = max (ans, dfs_calc (son, node, gen));
            dp[node] += dp[son];
            mx = max (mx, dp[son]);
        }
    dp[node] = max (is_gen, dp[node] - is_gen);
    ans = max ({ans, mx + is_gen, dp[node]});
    return ans;
}

int main() {
    ios::sync_with_stdio (false);
    cin.tie (0); cout.tie (0);
    int n;
    cin >> n;
    for (int i = 1; i < n; i++) {
        int x, y;
        cin >> x >> y;
        gr[x].pb (y);
        gr[y].pb (x);
    }
    string generators;
    cin >> generators; generators = " " + generators;
    cout << dfs_calc (1, 0, generators) << "\n";
    return 0;
}

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