oj.uz

Submission #478802

# Submission time Handle Problem Language Result Execution time Memory
478802 2021-10-08T12:14:19 Z nicolaalexandra Power Plant (JOI20_power) C++14
0 / 100
 3 ms 4996 KB 
#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++)
        for (auto vecin : L[i]){
            if (vecin == fth[i])
                continue;
            sol = max (sol,max(dp[i],dp[vecin] + f[i]));
        }

    cout<<sol;

    return 0;
}

Compilation message

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

Subtask #1
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 4996 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 41.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 4996 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 53.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 4996 KB Output isn't correct
2 Halted 0 ms 0 KB -