제출 #479884

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
479884		ogibogi2004	Biochips (IZhO12_biochips)	C++14	100 / 100	505 ms	422372 KiB

biochips

#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 / 100