oj.uz

Submission #346342

# Submission time Handle Problem Language Result Execution time Memory
346342 2021-01-09T12:21:07 Z nicolaalexandra Biochips (IZhO12_biochips) C++14
100 / 100
 755 ms 406536 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){

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

    for (auto vecin : L[nod]){

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

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

        for (int i=1;i<=min(m,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=1;j<=m;j++)
            dp[i][j] = -INF;

    dfs (rad);

    cout<<dp[rad][m];

    return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5100 KB Output is correct
2 Correct 4 ms 5100 KB Output is correct
3 Correct 4 ms 5228 KB Output is correct
4 Correct 20 ms 23020 KB Output is correct
5 Correct 22 ms 25324 KB Output is correct
6 Correct 23 ms 25324 KB Output is correct
7 Correct 430 ms 303212 KB Output is correct
8 Correct 421 ms 303268 KB Output is correct
9 Correct 598 ms 368476 KB Output is correct
10 Correct 755 ms 406536 KB Output is correct