Submission #1033531

#	Time	Username	Problem	Language	Result	Execution time	Memory
1033531		adaawf	Power Plant (JOI20_power)	C++17	100 / 100	84 ms	33168 KiB

power

#include <iostream>
#include <vector>
using namespace std;
int f[200005][2], a[200005];
vector<int> g[200005];
void dfs(int x, int p) {
    if (p != -1 && g[x].size() == 1) {
        f[x][0] = f[x][1] = a[x];
        return;
    }
    int c = 0, d = g[x].size() - (p != -1);
    if (d > 1) d = 1;
    else d = 0;
    for (int w : g[x]) {
        if (w == p) continue;
        dfs(w, x);
        c += f[w][1];
        f[x][0] = max(f[x][0], f[w][0]);
        f[x][0] = max(f[x][0], f[w][1] + a[x]);
    }
    f[x][1] = max(a[x], c - a[x]);
    f[x][0] = max(f[x][0], c - a[x] * d);
    //cout << x << " " << f[x][1] << " " << f[x][0] << '\n';
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n;
    cin >> n;
    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;
    s = " " + s;
    for (int i = 1; i <= n; i++) a[i] = (s[i] == '1');
    dfs(1, -1);
    cout << max(f[1][0], f[1][1]);
}

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