제출 #1265323

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1265323		phamtienhoang	Biochips (IZhO12_biochips)	C++20	30 / 100	501 ms	589824 KiB

biochips

#include <iostream>
#include <vector>
#include <map>
#include <string>
#include <algorithm>
#include <cassert>
#include <cstring>
#include <stack>
#include <set>
#include <cmath>
#include <queue>
#include <iomanip>
using namespace std;
const int N = 200002;
int f[N][502][2];
int a[N];
int sz[N];
int n , m;
vector<int> adj[N];
int root;

void dfs(int u , int p){
    f[u][1][1] = a[u];
    f[u][0][0] = 0;
    sz[u] = 1;
    for(int i = 0 ; i < adj[u].size() ; i++){
        int v = adj[u][i];
        if(v == p)
            continue;
        dfs(v, u);
        static int g[N];
        for(int i = 0 ; i <= min(sz[v] , m) ; i++){
            g[i] = max(f[v][i][0] , f[v][i][1]);
        }
        for(int s1 = min(sz[u] , m) ; s1 >= 0  ; s1--){
            for(int s2 = min(sz[v] , m) ; s2 >= 0 && (s2 + s1) <= m + 1 ; s2--){
                f[u][s1 + s2][0] = max(f[u][s1 + s2][0], f[u][s1][0] +  g[s2]);
            }
        }
        sz[u] += sz[v];
    }

    
}
int main(){
    cin >> n >> m;
    for(int i = 1; i <= n ;i++){
        int par;
        int val;
        cin >> par >> val;
        if(par == 0){
            root = i;
        }else{
            adj[i].push_back(par);
            adj[par].push_back(i);
        }
        a[i] = val;
    }
    dfs(root , -1);
    int ans = f[root][m][0];
    if(m == 1){
        ans = max(ans , f[root][m][1]);
    }
    cout << ans;
    return 0;
}

• Subtask 1: 30 / 100