oj.uz

답안 #479879

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
479879 2021-10-13T18:19:44 Z ogibogi2004 바이오칩 (IZhO12_biochips) C++14
0 / 100
 233 ms 410452 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++)
    {
        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[xd][j]=max(dp[xd][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
0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 233 ms 410452 KB Output is correct
2 Incorrect 180 ms 410436 KB Output isn't correct
3 Halted 0 ms 0 KB -