Submission #1206764

#	Time	Username	Problem	Language	Result	Execution time	Memory
1206764		Almonther	Biochips (IZhO12_biochips)	C++20	60 / 100	2104 ms	207488 KiB

biochips

#include"bits/stdc++.h"

using namespace std;
#define ll long long
#define co cout<<
// stuff
#pragma GCC optimize("O3,Ofast,unroll-loops")
#pragma GCC target("avx2,sse3,sse4,avx")
#pragma GCC target("popcnt")
const int maxn=2e5+5,maxm=501;
ll n,m;
vector<ll>v[maxn];
int arr[maxn];  
ll root=-1;
int values[maxn][maxm];
void dfs(ll x,ll last){
    vector<array<ll,3>>added;
    for(auto i:v[x]){
        if(i==last) continue;
        dfs(i,x);
        for(int j=1;j<=m;j++) added.push_back({i,values[i][j],j});
    }
    vector<pair<ll,ll>>apply;
    ll lastt=-1;
    for(auto[idx,val,wei]:added){
        if(idx!=lastt){
            lastt=idx;
            for(auto [id,what]:apply) values[x][id]=max(values[x][id],(int)what);
            apply.clear();
        }
        for(int i=m-wei;i>=0;i--){
            if((values[x][i]||i==0)&&values[x][i+wei]<values[x][i]+val) apply.push_back({i+wei,values[x][i]+val});
        }
    }
    for(auto [id,what]:apply) values[x][id]=max(values[x][id],(int)what);
    values[x][1]=max(values[x][1],arr[x]);
}
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: 60 / 100