Submission #763653

#	Time	Username	Problem	Language	Result	Execution time	Memory
763653		vjudge1	Power Plant (JOI20_power)	C++17	100 / 100	140 ms	26860 KiB

power

#include <bits/stdc++.h>

using namespace std;

int n;
vector<vector<int>> adjList;
vector<int> parent;
string isBased;

vector<int> dp;

int result = 0;

void depthFirstSearch(int u, int p)
{
    int V = 0;
    for (auto &v : adjList[u])
        if (v != p)
        {
            depthFirstSearch(v, u);
            dp[u] += dp[v];
            if (dp[v] > dp[V])
                V = v;
        }

    if (isBased[u] == '1')
    {
        result = max(dp[V] + 1, result);
        dp[u] = max(1, dp[u] - 1);
    }

    result = max(dp[u], result);
}

int main()
{
    // freopen("inp.txt", "r", stdin);

    ios::sync_with_stdio(false);

    cin >> n;
    adjList.resize(n + 1);
    parent.resize(n + 1);
    for (int u, v, i = 1; i < n; i++)
    {
        cin >> u >> v;
        adjList[u].emplace_back(v);
        adjList[v].emplace_back(u);
    }
    cin >> isBased;
    isBased = "!" + isBased;

    dp.resize(n + 1);
    depthFirstSearch(1, -1);

    cout << result;
}

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