oj.uz

답안 #346336

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
346336 2021-01-09T12:04:30 Z nicolaalexandra 바이오칩 (IZhO12_biochips) C++14
0 / 100
 42 ms 12780 KB 
#include <bits/stdc++.h>
#define DIM 200010
#define DIMM 210
using namespace std;

vector <int> L[DIM];
int dp[DIM][DIMM],v[DIM],cnt[DIM],aux[DIM];
int n,m,i,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;

    for (auto vecin : L[nod]){

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

        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;
    }

    dfs (rad);

    cout<<dp[rad][m];

    return 0;
}

Subtask #1
0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 5228 KB Output is correct
2 Correct 3 ms 5100 KB Output is correct
3 Correct 4 ms 5100 KB Output is correct
4 Incorrect 42 ms 12780 KB Output isn't correct
5 Halted 0 ms 0 KB -