제출 #1172405

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1172405		chikien2009	Power Plant (JOI20_power)	C++20	100 / 100	161 ms	19512 KiB

power

#include <bits/stdc++.h>

using namespace std;

void setup()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

int n, a, b, f[200000], h[200000], res;
string s;
vector<int> g[200000];
bool valid[200000];

inline void DFS1(int node, int par)
{
    h[node] = 0;
    for (auto &i : g[node])
    {
        if (i != par)
        {
            DFS1(i, node);
            h[node] += f[i];
        }
    }
    f[node] = max(h[node] - valid[node], (int)valid[node]);
}

inline void DFS2(int node, int par, int cur)
{
    res = max(res, f[node] + cur);
    for (auto & i : g[node])
    {
        if (i != par)
        {
            DFS2(i, node, max((int)valid[node], h[node] - f[i] + cur - valid[node]));
        }
    }
}

int main()
{
    setup();

    cin >> n;
    for (int i = 0; i < n - 1; ++i)
    {
        cin >> a >> b;
        g[a - 1].push_back(b - 1);
        g[b - 1].push_back(a - 1);
    }
    cin >> s;
    for (int i = 0; i < n; ++i)
    {
        valid[i] = (s[i] == '1');
    }
    DFS1(0, 0);
    DFS2(0, 0, 0);
    cout << res;
    return 0;
}

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