Submission #425251

#	Time	Username	Problem	Language	Result	Execution time	Memory
425251		Runtime_error_	Biochips (IZhO12_biochips)	C++14	100 / 100	586 ms	21368 KiB

biochips

#include <bits/stdc++.h>
#define pb push_back
using namespace std;
const int N = 2e5+9,M = 209;
int n,m,root,val[N];
vector<int> adj[N];
vector<int> dp[N];

vector<int> merge(vector<int> a,vector<int> b){
    int sza = a.size(),szb = b.size();

    vector<int> ret(min(m,sza+szb)+1,0);
    for(int i=0;i<sza;i++)
        for(int j=0;j<szb;j++)
            if(i+j <= m)
                ret[i+j] = max(ret[i+j],a[i]+b[j]);
    return ret;
}

void dfs(int u,int p){
    dp[u].resize(1,0);
    for(auto v:adj[u]){
        if(v == p)continue;
        dfs(v,u);
        dp[u] = merge(dp[u],dp[v]);
    }
    if(dp[u].size() == 1)
        dp[u].pb(0);

    dp[u][1] = max(dp[u][1],val[u]);
//    cout<<u<<" ::";
//    for(int i=0;i<dp[u].size();i++)
//        cout<<dp[u][i]<<" ";
//    cout<<endl;
}

int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        int par;
        scanf("%d%d",&par,val+i);
        if(par != 0)
            adj[par].pb(i);
        else
            root = i;
    }
    dfs(root,0);
    cout<<dp[root][m]<<endl;
}

Compilation message (stderr)

biochips.cpp: In function 'int main()':
biochips.cpp:40:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |     scanf("%d%d",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~
biochips.cpp:43:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |         scanf("%d%d",&par,val+i);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100