Submission #1111074

#	Time	Username	Problem	Language	Result	Execution time	Memory
1111074		tymoneq	Power Plant (JOI20_power)	C++17	0 / 100	3 ms	5712 KiB

power

#include <bits/stdc++.h>

using namespace std;

constexpr int N = 2e5 + 10;

vector<int> adj[N];
bool hasPowerPlant[N];
int dp[N];

inline void calc(int v, int p)
{
    for (int w : adj[v])
        if (w != p)
            calc(w, v);

    int sum = 0;
    for (int w : adj[v])
        if (w != p)
            sum += dp[w];

    if (hasPowerPlant[v] && adj[v].size() > 1)
        dp[v] = max(1, sum - 1);

    else if (hasPowerPlant[v] && adj[v].size() == 1)
        dp[v] = max(1, sum + 1);

    else
        dp[v] = sum;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n;
    cin >> n;

    for (int i = 1; i < n; i++)
    {
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }

    for (int i = 1; i <= n; i++)
    {
        char a;
        cin >> a;
        if (a - '0' == 1)
            hasPowerPlant[i] = 1;
    }

    calc(1, 1);

    cout << dp[1] << "\n";

    return 0;
}

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