Submission #478805

#	Time	Username	Problem	Language	Result	Execution time	Memory
478805		nicolaalexandra	Power Plant (JOI20_power)	C++14	100 / 100	324 ms	29552 KiB

power

#include <bits/stdc++.h>
#define DIM 200010
using namespace std;

/// dp[nod] - profit maxim daca iau doar noduri care nu sunt stramosi intre ele

vector <int> L[DIM];
int dp[DIM],f[DIM],cnt[DIM],fth[DIM];
char s[DIM];
int n,x,y,i;

void dfs (int nod, int tata){

    fth[nod] = tata;
    cnt[nod] = f[nod];
    int ok = 0;
    for (auto vecin : L[nod])
        if (vecin != tata){
            ok = 1;
            dfs (vecin,nod);
            cnt[nod] += cnt[vecin];
        }

    if (!ok){
        if (f[nod])
            dp[nod] = 1;
    } else {
        for (auto vecin : L[nod]){
            if (vecin != tata)
                dp[nod] += dp[vecin];
        }

        dp[nod] -= f[nod];

        if (f[nod])
            dp[nod] = max (dp[nod],1);
    }

}

int main (){

    //ifstream cin ("date.in");
    //ofstream cout ("date.out");

    cin>>n;
    for (i=1;i<n;i++){
        cin>>x>>y;
        L[x].push_back(y);
        L[y].push_back(x);
    }

    cin>>s+1;

    for (i=1;i<=n;i++)
        f[i] = s[i] - '0';


    dfs (1,0);

    int sol = 0;
    for (i=1;i<=n;i++){
        sol = max (sol,dp[i]);
        for (auto vecin : L[i]){
            if (vecin == fth[i])
                continue;
            sol = max (sol,dp[vecin] + f[i]);
        }
    }

    cout<<sol;

    return 0;
}

Compilation message (stderr)

power.cpp: In function 'int main()':
power.cpp:53:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   53 |     cin>>s+1;
      |          ~^~

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