oj.uz

Submission #140365

# Submission time Handle Problem Language Result Execution time Memory
140365 2019-08-02T16:09:44 Z rzbt Biochips (IZhO12_biochips) C++14
100 / 100
 435 ms 11640 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Correct 6 ms 4984 KB Output is correct
3 Correct 8 ms 5112 KB Output is correct
4 Correct 13 ms 5368 KB Output is correct
5 Correct 13 ms 5496 KB Output is correct
6 Correct 14 ms 5368 KB Output is correct
7 Correct 225 ms 10512 KB Output is correct
8 Correct 227 ms 10616 KB Output is correct
9 Correct 331 ms 11128 KB Output is correct
10 Correct 435 ms 11640 KB Output is correct