oj.uz

Submission #1111074

# Submission time Handle Problem Language Result Execution time Memory
1111074 2024-11-11T12:17:10 Z tymoneq Power Plant (JOI20_power) C++17
0 / 100
 3 ms 5712 KB 
#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.0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 5712 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 41.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 5712 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 53.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 5712 KB Output isn't correct
2 Halted 0 ms 0 KB -