Submission #702350

#	Time	Username	Problem	Language	Result	Execution time	Memory
702350		leeh18	Power Plant (JOI20_power)	C++17	100 / 100	198 ms	33672 KiB

power

#include <bits/stdc++.h>
using namespace std;

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int n;
    cin >> n;
    vector<vector<int>> adj(n);
    for (auto i = 0; i < n - 1; ++i) {
        int u, v;
        cin >> u >> v;
        --u, --v;
        adj[u].emplace_back(v);
        adj[v].emplace_back(u);
    }
    vector<bool> s(n);
    auto ans = 0;
    for (auto i = 0; i < n; ++i) {
        char c;
        cin >> c;
        s[i] = (c == '1');
        ans += int(s[i]);
    }
    ans = min(ans, 2);
    vector<int> dp(n), sum(n);
    auto f = [&](auto self, int u, int p) -> int {
        for (auto v : adj[u]) {
            if (v != p) {
                sum[u] += self(self, v, u);
            }
        }
        dp[u] = (s[u] ? max(sum[u] - 1, 1) : sum[u]);
        return dp[u];
    };
    f(f, 0, 0);
    vector<int> dp_reroot(n), sum_reroot(n);
    auto f_reroot = [&](auto self, int u, int p) -> void {
        if (u == p) {
            dp_reroot[u] = dp[u];
            sum_reroot[u] = sum[u];
        } else {
            sum_reroot[u] = sum[u] + (s[p] ? max(sum_reroot[p] - sum[u] - 1, 1)
                                           : sum_reroot[p] - sum[u]);
            dp_reroot[u] = (s[u] ? max(sum_reroot[u] - 1, 1) : sum_reroot[u]);
        }
        for (auto v : adj[u]) {
            if (v != p) {
                self(self, v, u);
            }
        }
    };
    f_reroot(f_reroot, 0, 0);
    ans = max(ans, *max_element(begin(dp_reroot), end(dp_reroot)));
    cout << ans << "\n";
}

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