Submission #90131

#	Time	Username	Problem	Language	Result	Execution time	Memory
90131		Bodo171	Biochips (IZhO12_biochips)	C++14	100 / 100	660 ms	17088 KiB

biochips

#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
const int nmax=200005;
vector<int> v[nmax];
int dp[2][nmax];
int rep[nmax],l[nmax],r[nmax],val[nmax];
int n,m,i,j,nr,tt,x,use;
void dfs(int x)
{
    rep[++nr]=x;l[x]=nr;
    for(int i=0;i<v[x].size();i++)
        dfs(v[x][i]);
    r[x]=nr;
}
int main()
{
   // freopen("data.in","r",stdin);
    ios_base::sync_with_stdio(false);
    cin>>n>>m;
    for(i=1;i<=n;i++)
    {
        cin>>tt>>val[i];
        v[tt].push_back(i);
    }
    dfs(v[0][0]);
    for(i=0;i<=m;i++)
    {
      use=1-use;
      for(j=0;j<=n;j++)
        dp[1-use][j]=-(1<<30);
        for(j=1;j<=n;j++)
      {
        x=rep[j];
        dp[use][j]=max(dp[use][j],dp[use][j-1]);
        dp[1-use][r[x]]=max(dp[use][l[x]-1]+val[x],dp[1-use][r[x]]);
      }
    }
    cout<<dp[use][n];
    return 0;
}

Compilation message (stderr)

biochips.cpp: In function 'void dfs(int)':
biochips.cpp:13:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<v[x].size();i++)
                 ~^~~~~~~~~~~~
biochips.cpp: In function 'int main()':
biochips.cpp:31:7: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
       for(j=0;j<=n;j++)
       ^~~
biochips.cpp:33:9: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
         for(j=1;j<=n;j++)
         ^~~

• Subtask 1: 100 / 100