oj.uz

Submission #425251

# Submission time Handle Problem Language Result Execution time Memory
425251 2021-06-12T17:29:19 Z Runtime_error_ Biochips (IZhO12_biochips) C++14
100 / 100
 586 ms 21368 KB 

#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

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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9676 KB Output is correct
2 Correct 6 ms 9676 KB Output is correct
3 Correct 6 ms 9676 KB Output is correct
4 Correct 13 ms 10400 KB Output is correct
5 Correct 18 ms 10316 KB Output is correct
6 Correct 19 ms 10372 KB Output is correct
7 Correct 375 ms 17884 KB Output is correct
8 Correct 423 ms 17936 KB Output is correct
9 Correct 491 ms 20192 KB Output is correct
10 Correct 586 ms 21368 KB Output is correct