oj.uz

Submission #925047

# Submission time Handle Problem Language Result Execution time Memory
925047 2024-02-10T14:07:23 Z boris_mihov Power Plant (JOI20_power) C++17
0 / 100
 2 ms 8796 KB 
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <cstring>
#include <vector>
#include <queue>
#include <stack>
#include <set>

typedef long long llong;
const int MAXN = 2e5 + 10;
const int INF  = 2e9;

int n;
int a[MAXN];
int b[MAXN];
int sz[MAXN];
char s[MAXN];
int dp[MAXN][2];
bool bl[MAXN][2];
std::vector <int> g[MAXN];

void buildDFS(int node, int par)
{
    for (int &u : g[node])
    {
        if (u == par)
        {
            std::swap(u, g[node].back());
            g[node].pop_back();
            break;
        }
    }

    sz[node] = s[node] - '0';
    for (const int &u : g[node])
    {
        buildDFS(u, node);
        sz[node] += sz[u];
    }
}

int f(int node, bool parentHas)
{
    if (bl[node][parentHas])
    {
        return dp[node][parentHas];
    }

    bl[node][parentHas] = true;
    dp[node][parentHas] = std::max(dp[node][parentHas], (int)(s[node] == '1'));

    if (!parentHas && s[node] == '1')
    {
        for (const int &u : g[node])
        {
            dp[node][parentHas] = std::max(dp[node][parentHas], f(u, true) + 1);
        }
    }

    for (const int &u : g[node])
    {
        dp[node][parentHas] = std::max(dp[node][parentHas], f(u, false));
    }

    int curr = 0;
    for (const int &u : g[node])
    {
        curr += f(u, true);    
    }

    dp[node][parentHas] = std::max(dp[node][parentHas], curr - (s[node] == '1'));
    return dp[node][parentHas];
}

void solve()
{
    buildDFS(1, 0);
    std::cout << f(1, 0) << '\n';
}

void input()
{
    std::cin >> n;
    for (int i = 1 ; i < n ; ++i)
    {
        int u, v;
        std::cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    std::cin >> s + 1;
}

void fastIOI()
{
    std::ios_base :: sync_with_stdio(0);
    std::cout.tie(nullptr);
    std::cin.tie(nullptr);
}   

int main()
{
    fastIOI();
    input();
    solve();

    return 0;
}

Compilation message

power.cpp: In function 'void input()':
power.cpp:94:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   94 |     std::cin >> s + 1;
      |                 ~~^~~

Subtask #1
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8792 KB Output is correct
2 Correct 1 ms 8792 KB Output is correct
3 Correct 2 ms 8796 KB Output is correct
4 Correct 2 ms 8796 KB Output is correct
5 Correct 1 ms 8796 KB Output is correct
6 Correct 2 ms 8796 KB Output is correct
7 Incorrect 1 ms 8796 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8792 KB Output is correct
2 Correct 1 ms 8792 KB Output is correct
3 Correct 2 ms 8796 KB Output is correct
4 Correct 2 ms 8796 KB Output is correct
5 Correct 1 ms 8796 KB Output is correct
6 Correct 2 ms 8796 KB Output is correct
7 Incorrect 1 ms 8796 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8792 KB Output is correct
2 Correct 1 ms 8792 KB Output is correct
3 Correct 2 ms 8796 KB Output is correct
4 Correct 2 ms 8796 KB Output is correct
5 Correct 1 ms 8796 KB Output is correct
6 Correct 2 ms 8796 KB Output is correct
7 Incorrect 1 ms 8796 KB Output isn't correct
8 Halted 0 ms 0 KB -