Submission #1028973

#	Time	Username	Problem	Language	Result	Execution time	Memory
1028973		raphaelp	Power Plant (JOI20_power)	C++14	100 / 100	191 ms	31524 KiB

power

#include <bits/stdc++.h>
using namespace std;
void dfs(int x, int p, vector<vector<int>> &AR, string &S, vector<int> &dp)
{
    for (int i = 0; i < AR[x].size(); i++)
    {
        if (AR[x][i] == p)
            continue;
        dfs(AR[x][i], x, AR, S, dp);
        dp[x] += dp[AR[x][i]];
    }
    if (S[x] == '1')
        dp[x] = max(dp[x] - 1, 1);
}
void dfs2(int x, int p, vector<vector<int>> &AR, vector<int> &dp, string &S, int val)
{
    dp[x] += val;
    int sum = 0, best = 0;
    for (int i = 0; i < AR[x].size(); i++)
    {
        if (AR[x][i] == p)
            continue;
        sum += dp[AR[x][i]];
        best = max(best, dp[AR[x][i]]);
    }
    sum += val;
    best = max(best, val);
    if (S[x] == '1')
    {
        dp[x] = max(sum - 1, best + 1);
    }
    for (int i = 0; i < AR[x].size(); i++)
    {
        if (AR[x][i] == p)
            continue;
        int next = sum - dp[AR[x][i]];
        if (S[x] == '1')
            next = max(next - 1, 1);
        dfs2(AR[x][i], x, AR, dp, S, next);
    }
}
int main()
{
    int N;
    cin >> N;
    vector<vector<int>> AR(N);
    for (int i = 0; i < N - 1; i++)
    {
        int a, b;
        cin >> a >> b;
        a--, b--;
        AR[a].push_back(b);
        AR[b].push_back(a);
    }
    string S;
    cin >> S;
    vector<int> dp(N);
    dfs(0, 0, AR, S, dp);
    dfs2(0, 0, AR, dp, S, 0);
    int best = 0;
    for (int i = 0; i < N; i++)
        best = max(best, dp[i]);
    cout << best;
}

Compilation message (stderr)

power.cpp: In function 'void dfs(int, int, std::vector<std::vector<int> >&, std::string&, std::vector<int>&)':
power.cpp:5:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 |     for (int i = 0; i < AR[x].size(); i++)
      |                     ~~^~~~~~~~~~~~~~
power.cpp: In function 'void dfs2(int, int, std::vector<std::vector<int> >&, std::vector<int>&, std::string&, int)':
power.cpp:19:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |     for (int i = 0; i < AR[x].size(); i++)
      |                     ~~^~~~~~~~~~~~~~
power.cpp:32:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     for (int i = 0; i < AR[x].size(); i++)
      |                     ~~^~~~~~~~~~~~~~

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