Submission #1283384

#	Time	Username	Problem	Language	Result	Execution time	Memory
1283384		am_aadvik	Power Plant (JOI20_power)	C++20	100 / 100	182 ms	44684 KiB

power

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

vector<int> g[2000005], p;
int dp[2000005][2];
int dfs(int node, int b, int par) {
    if (dp[node][b] != -1) return dp[node][b];
    int mc1 = 0, mc0 = 0, sc1 = 0;
    for (auto x : g[node])
        if (x != par) {
            mc1 = max(mc1, dfs(x, 1, node));
            sc1 += dfs(x, 1, node);
            mc0 = max(mc0, dfs(x, 0, node));
        }
    int c1 = ((b == 0) ? mc1 : 0) + p[node];
    int c2 = ((b == 0) ? mc0 : 0);
    int c3 = ((b == 0) ? max(sc1, mc0) : sc1) - p[node];
    return dp[node][b] = max(c1, max(c2, c3));
}
int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int n; cin >> n; p.assign(n + 1, 0);
    for (int i = 1; i < n; ++i) {
        int u, v; cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    string s; cin >> s;
    for (int i = 1; i <= n; ++i)
        p[i] = (s[i - 1] - '0');
    memset(dp, -1, sizeof(dp));
    cout << dfs(1, 0, 0) << '\n';
}

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