Submission #1206883

#	Time	Username	Problem	Language	Result	Execution time	Memory
1206883		Almonther	Biochips (IZhO12_biochips)	C++20	100 / 100	494 ms	405308 KiB

biochips

#include"bits/stdc++.h"

using namespace std;
#define ll long long
#define co cout<<
// stuff
const int maxn=2e5+1,maxm=501;
int n,m;
vector<ll>v[maxn];
int arr[maxn];  
ll root=-1;
int values[maxn][maxm];
int mx[maxn];
void dfs(ll x,ll last){
    for(auto i:v[x]){
        if(i==last) continue;
        dfs(i,x);
        vector<pair<int,int>>added;
        for(int j=mx[x];j>=0;j--){
            for(int k=min(mx[i],m-j);k>=0;k--){
                if(values[x][j]+values[i][k]>values[x][j+k]) added.push_back({j,k});
            }
        }
        mx[x]+=mx[i];
        mx[x]=min(mx[x],m);
        for(auto [j,k]:added){
            values[x][j+k]=max(values[x][j+k],values[x][j]+values[i][k]);
        }
    }
    values[x][1]=max(values[x][1],arr[x]);
    mx[x]=max(mx[x],1);
}
void solve(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        ll a;
        cin>>a>>arr[i];
        if(a==0){
            root=i;
            continue;
        }
        v[i].push_back(a);
        v[a].push_back(i);
    }
    dfs(root,-1);
    co values[root][m];
}

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int _=1;
    // cin>>_;
    while(_--) solve();
}

• Subtask 1: 100 / 100