Submission #140365

#	Time	Username	Problem	Language	Result	Execution time	Memory
140365		rzbt	Biochips (IZhO12_biochips)	C++14	100 / 100	435 ms	11640 KiB

biochips

#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define MAXN 200005
typedef long long ll;

using namespace std;

int n,m;
vector<int> niz[MAXN];
int w[MAXN];
int koren;
int vreme;
int ulaz[MAXN],tezina[MAXN];
int dp[MAXN],dpp[MAXN];
void dfs(int t){
    int tulaz=vreme;
    for(auto x:niz[t])
        dfs(x);
    vreme++;
    ulaz[vreme]=tulaz;
    tezina[vreme]=w[t];
}



int main()
{
    scanf("%d %d", &n, &m);
    for(int i=1;i<=n;i++){
        int o,tezina;
        scanf("%d %d", &o, &tezina);
        if(o==0)koren=i;
        else niz[o].pb(i);
        w[i]=tezina;
    }
    dfs(koren);
    dp[0]=dpp[0]=-1e9;
    for(int i=1;i<=n;i++)dpp[i]=max(tezina[i],dpp[i-1]);
    for(int j=1;j<m;j++){
        for(int i=1;i<=n;i++)dp[i]=max(tezina[i]+dpp[ulaz[i]],dp[i-1]);
        //for(int i=1;i<=n;i++) printf("%d ",dp[i]);
        for(int i=1;i<=n;i++)dpp[i]=dp[i];
        //printf("\n");

    }
    printf("%d",dp[n]);

}

Compilation message (stderr)

biochips.cpp: In function 'int main()':
biochips.cpp:32:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~~
biochips.cpp:35:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &o, &tezina);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100