Submission #702345

#	Time	Username	Problem	Language	Result	Execution time	Memory
702345		leeh18	Power Plant (JOI20_power)	C++17	47 / 100	1586 ms	14152 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);
    auto f = [&](auto self, int u, int p) -> int {
        auto sum = 0;
        for (auto v : adj[u]) {
            if (v != p) {
                sum += self(self, v, u);
            }
        }
        return (s[u] ? max(sum - 1, 1) : sum);
    };
    for (auto i = 0; i < n; ++i) {
        ans = max(ans, f(f, i, i));
    }
    cout << ans << "\n";
}

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