Submission #358517

#	Time	Username	Problem	Language	Result	Execution time	Memory
358517		BartolM	Power Plant (JOI20_power)	C++17	100 / 100	315 ms	30188 KiB

power

#include <bits/stdc++.h>

using namespace std;

#define X first
#define Y second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <int, pii> pip;
typedef pair <pii, int> ppi;
typedef pair <ll, ll> pll;

const int INF=0x3f3f3f3f;
const int N=2e5+5;

int n;
vector <int> ls[N];
int val[N], un[N], iz[N];
int sol=0;

void dfs(int node, int par) {
    un[node]=val[node];
    int uk=0;
    for (int sus:ls[node]) {
        if (sus==par) continue;
        dfs(sus, node);
        uk+=un[sus];
    }
    un[node]=max(un[node], uk-val[node]);
}

void rek(int node, int par) {
    int uk=iz[node];
    for (int sus:ls[node]) if (sus!=par) uk+=un[sus];

    for (int sus:ls[node]) {
        if (sus==par) continue;
        iz[sus]=max(val[node], uk-un[sus]-val[node]);
        rek(sus, node);
    }
    if (val[node]) {
        sol=max(sol, uk-1);
        sol=max(sol, iz[node]+1);
        for (int sus:ls[node]) if (sus!=par) sol=max(sol, un[sus]+1);
    }
}

void load() {
    scanf("%d", &n);
    for (int i=0; i<n-1; ++i) {
        int a, b;
        scanf("%d %d", &a, &b);
        ls[a].pb(b); ls[b].pb(a);
    }
    for (int i=1; i<=n; ++i) {
        char c;
        scanf(" %c", &c);
        val[i]=c-'0';
    }
}

int main() {
    load();

    dfs(1, 0);
    rek(1, 0);
//    for (int i=1; i<=n; ++i) {
//        printf("i: %d, un: %d, iz: %d\n",i, un[i], iz[i]);
//    }
    printf("%d\n", sol);
    return 0;
}

Compilation message (stderr)

power.cpp: In function 'void load()':
power.cpp:51:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   51 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
power.cpp:54:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   54 |         scanf("%d %d", &a, &b);
      |         ~~~~~^~~~~~~~~~~~~~~~~
power.cpp:59:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   59 |         scanf(" %c", &c);
      |         ~~~~~^~~~~~~~~~~

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