oj.uz

Submission #387548

# Submission time Handle Problem Language Result Execution time Memory
387548 2021-04-09T00:02:13 Z timmyfeng Power Plant (JOI20_power) C++17
0 / 100
 3 ms 4940 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 200001;

int profit[N], ans;
vector<int> adj[N];
string power;

void dfs_pull(int u, int p = 0) {
    profit[u] = '0' - power[u];
    for (auto c : adj[u]) {
        if (c != p) {
            dfs_pull(c, u);
            profit[u] += profit[c];
        }
    }
    profit[u] = max(profit[u], power[u] - '0');
}

void dfs_push(int u, int p = 0) {
    profit[u] = '0' - power[u];
    for (auto c : adj[u]) {
        profit[u] += profit[c];
    }

    ans = max(ans, profit[u]);

    for (auto c : adj[u]) {
        if (c != p) {
            int prv = profit[u];
            profit[u] = max(profit[u] - profit[c], power[u] - '0');
            dfs_push(c, u);
            profit[u] = prv;
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    cin >> power;
    power = " " + power;

    dfs_pull(1);
    dfs_push(1);

    cout << ans << "\n";
}

Subtask #1
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 4940 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 41.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 4940 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 53.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 4940 KB Output isn't correct
2 Halted 0 ms 0 KB -