Submission #1206870

#	Time	Username	Problem	Language	Result	Execution time	Memory
1206870		FaresSTH	Biochips (IZhO12_biochips)	C++20	0 / 100	2105 ms	220500 KiB

biochips

#include"bits/stdc++.h"
using namespace std;
using ll=long long;
#define S second
#define F first
int x[200001],s[200001],dp[200001][501],t[501],n,m,rt;
vector<int>g[200001];
void dfs(int u,int p){
    s[u]=1;
    for(int v:g[u])if(v!=p){
        dfs(v,u);
        s[u]+=s[v];
    }
    for(int v:g[u])if(v!=p){
        for(int i=0;i<=m;i++){
            for(int j=0;j<=m-i;j++){
                if(dp[u][i+j]<dp[u][i]+dp[v][j]&&dp[u][i]&&dp[v][j])t[i+j]=dp[u][i]+dp[v][j];
            }
        }
        for(int i=0;i<=m;i++)dp[u][i]=max(dp[u][i],t[i]),t[i]=0;
        dp[u][1]=max(dp[u][1],dp[v][1]);
    }
    dp[u][1]=max(dp[u][1],x[u]);
}
int main(){
    cin.tie(0)->sync_with_stdio(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        int p,v;
        cin>>p>>v;
        if(p)g[p].push_back(i),g[i].push_back(p);
        else rt=i;
        x[i]=v;
    }
    dfs(rt,0);
    cout<<dp[rt][m-1];
}

• Subtask 1: 0 / 100