Submission #518426

#	Time	Username	Problem	Language	Result	Execution time	Memory
518426		Vladth11	Power Plant (JOI20_power)	C++14	100 / 100	175 ms	32328 KiB

power

#include <bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "

using namespace std;
typedef long long ll;
typedef pair <ll, ll> pii;
typedef pair <long double, pii> muchie;

const ll NMAX = 200001;
const ll VMAX = 21;
const ll INF = (1LL << 60);
const ll MOD = 1000000007;
const ll BLOCK = 318;
const ll base = 31;
const ll nr_of_bits = 60;

vector <int> v[NMAX];
string s;
int dp[NMAX][2];

void DFS(int node, int p){
    if(s[node - 1] == '1'){
        dp[node][1] = 1;
    }
    int maxim = -2e9, maxim1 = -2e9, maxim2 = 0, sum = 0;
    for(auto x : v[node]){
        if(x == p)
            continue;
        DFS(x, node);
        maxim = max(maxim, dp[x][2]);
        maxim1 = max(maxim1, dp[x][1]);
        sum += dp[x][1];
    }
    dp[node][2] = maxim;
    dp[node][2] = max(dp[node][2], maxim1 + (s[node - 1] == '1')); /// il iau pe cel mai de sus
    dp[node][1] = max(dp[node][1], sum - (s[node - 1] == '1'));
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, i;
    cin >> n;
    for(i = 1; i < n; i++){
        int x, y;
        cin >> x >> y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    cin >> s;
    DFS(1, 0);
    cout << max(dp[1][1], dp[1][2]);
    return 0;
}

Compilation message (stderr)

power.cpp: In function 'void DFS(int, int)':
power.cpp:26:38: warning: unused variable 'maxim2' [-Wunused-variable]
   26 |     int maxim = -2e9, maxim1 = -2e9, maxim2 = 0, sum = 0;
      |                                      ^~~~~~
power.cpp:35:15: warning: array subscript 2 is above array bounds of 'int [2]' [-Warray-bounds]
   35 |     dp[node][2] = maxim;
      |     ~~~~~~~~~~^
power.cpp:36:15: warning: array subscript 2 is above array bounds of 'int [2]' [-Warray-bounds]
   36 |     dp[node][2] = max(dp[node][2], maxim1 + (s[node - 1] == '1')); /// il iau pe cel mai de sus
      |     ~~~~~~~~~~^
power.cpp:31:35: warning: array subscript 2 is above array bounds of 'int [2]' [-Warray-bounds]
   31 |         maxim = max(maxim, dp[x][2]);
      |                            ~~~~~~~^

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