Submission #595342

#	Time	Username	Problem	Language	Result	Execution time	Memory
595342		elkernos	Power Plant (JOI20_power)	C++17	100 / 100	179 ms	31552 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>> g(n + 1);
    for(int i = 1; i < n; i++) {
        int a, b;
        cin >> a >> b;
        g[a].emplace_back(b);
        g[b].emplace_back(a);
    }
    string s;
    cin >> s;
    s = "#" + s;
    vector<int> dp(n + 1);
    int ans = 0;
    function<void(int, int)> dfs = [&](int u, int p) {
        int sum = 0;
        for(int to : g[u]) {
            if(to == p) {
                continue;
            }
            dfs(to, u);
            sum += dp[to];
            if(s[u] == '1') {
                ans = max(ans, dp[to] + 1);
            }
        }
        dp[u] = sum;
        if(s[u] == '1') {
            dp[u]--;
            dp[u] = max(dp[u], 1);
        }
        ans = max(ans, dp[u]);
    };
    dfs(1, 1);
    cout << ans << '\n';
}

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