oj.uz

Submission #346341

# Submission time Handle Problem Language Result Execution time Memory
346341 2021-01-09T12:10:57 Z nicolaalexandra Biochips (IZhO12_biochips) C++14
0 / 100
 42 ms 23020 KB 
#include <bits/stdc++.h>
#define DIM 200010
#define DIMM 510
#define INF 2000000000
using namespace std;

vector <int> L[DIM];
int dp[DIM][DIMM],v[DIM],cnt[DIM],aux[DIM];
int n,m,i,j,x,rad;

void dfs (int nod){

    for (auto vecin : L[nod]){
        dfs (vecin);
        cnt[nod] += cnt[vecin];
    }

    if (L[nod].empty()) /// frunza
        cnt[nod] = 1;

    dp[nod][0] = 0;

    for (auto vecin : L[nod]){

        for (int i=1;i<=cnt[nod];i++)
            aux[i] = -INF;

        for (int i=1;i<=cnt[vecin];i++) /// cat elimin din subarborele asta
            for (int j=cnt[nod];j>=i;j--)
                aux[j] = max (aux[j],dp[nod][j-i] + dp[vecin][i]);

        for (int i=1;i<=cnt[nod];i++)
            dp[nod][i] = max (dp[nod][i],aux[i]);
    }

    dp[nod][1] = max(dp[nod][1],v[nod]);

}

int main (){

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

    cin>>n>>m;
    for (i=1;i<=n;i++){
        cin>>x>>v[i];
        if (x)
            L[x].push_back(i);
        else rad = i;
    }

    for (i=1;i<=n;i++)
        for (j=0;j<=m;j++)
            dp[i][j] = -INF;

    dfs (rad);

    cout<<dp[rad][m];

    return 0;
}

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5100 KB Output is correct
2 Correct 3 ms 5100 KB Output is correct
3 Correct 4 ms 5228 KB Output is correct
4 Incorrect 42 ms 23020 KB Output isn't correct
5 Halted 0 ms 0 KB -