oj.uz

Submission #479884

# Submission time Handle Problem Language Result Execution time Memory
479884 2021-10-13T18:43:01 Z ogibogi2004 Biochips (IZhO12_biochips) C++14
100 / 100
 505 ms 422372 KB 
#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e5+6;
const int MAXM=512;
int n,m;
int x[MAXN];
int dp[MAXN][MAXM];
vector<int>g[MAXN];
int tin[MAXN],tout[MAXN],root,t=0,x1[MAXN];
void dfs(int u)
{
    tin[u]=++t;
    x1[tin[u]]=x[u];
    for(auto xd:g[u])
    {
        dfs(xd);
    }
    tout[u]=t;
}
vector<int>f[MAXN];
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        int par;
        cin>>par>>x[i];
        if(par==0)root=i;
        else g[par].push_back(i);
    }
    dfs(root);
    for(int i=1;i<=n;i++)
    {
        //cout<<"node  "<<tin[i]<<" "<<tout[i]<<endl;
        f[tout[i]].push_back(tin[i]);
    }
    memset(dp,-1,sizeof(dp));
    dp[0][0]=0;
    for(int i=1;i<=n;i++)
    {
        for(auto xd:f[i])
        {
            for(int j=1;j<=m;j++)
            {
                if(dp[xd-1][j-1]!=-1)dp[i][j]=max(dp[i][j],dp[xd-1][j-1]+x1[xd]);
            }
        }
        for(int j=0;j<=m;j++)
        {
            if(dp[i-1][j]!=-1)
            {
                dp[i][j]=max(dp[i][j],dp[i-1][j]);
            }
            /*if(dp[i][j]!=-1)
            {
                cout<<i<<" "<<j<<" "<<dp[i][j]<<endl;
            }*/
        }
    }
    cout<<dp[n][m]<<endl;
return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 213 ms 410508 KB Output is correct
2 Correct 166 ms 410408 KB Output is correct
3 Correct 169 ms 410532 KB Output is correct
4 Correct 171 ms 410984 KB Output is correct
5 Correct 178 ms 411056 KB Output is correct
6 Correct 188 ms 410964 KB Output is correct
7 Correct 392 ms 419872 KB Output is correct
8 Correct 385 ms 419872 KB Output is correct
9 Correct 440 ms 421384 KB Output is correct
10 Correct 505 ms 422372 KB Output is correct