Submission #1097080

#	Time	Username	Problem	Language	Result	Execution time	Memory
1097080		anmattroi	Power Plant (JOI20_power)	C++14	100 / 100	83 ms	28760 KiB

power

#include <bits/stdc++.h>

#define maxn 200005

using namespace std;

int n;
vector<int> adj[maxn];
int f[maxn], g[maxn];

char a[maxn];
int ds = 0;
int E[maxn];


void dfs(int u, int dad) {
    int sum = 0, mx = 0;
    for (int v : adj[u]) {
        if (v == dad) continue;
        dfs(v, u);
        mx = max(mx, f[v]);
        sum += f[v];
    }
    if (E[u] == 1) ds = max(ds, max(mx+1, sum-1));
    else ds = max(ds, sum);
    f[u] = max(E[u], sum-E[u]);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        if (a[i] == '1') E[i] = 1;
    }
    dfs(1, 0);
    cout << ds;

}

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