oj.uz

Submission #16857

# Submission time Handle Problem Language Result Execution time Memory
16857 2015-10-23T16:55:22 Z hasanb Biochips (IZhO12_biochips) C++
100 / 100
 255 ms 479364 KB 
#include<bits/stdc++.h>

using namespace std;
#define FORR(ii,aa,bb) for(int ii=aa;ii<bb;ii++)
#define FOR(ii,aa,bb) for(int ii=aa;ii<=bb;ii++)
#define ROF(ii,aa,bb) for(int ii=aa;ii>=bb;ii--)

#define dbg(x) cerr << (#x) << " --> " << (x) << endl
#define ll long long
#define pii pair<int,int>
#define mod 1000000007
#define N (int)(2e5+10)
#define mp make_pair
#define pb push_back
#define sd second
#define ft first
#define endll puts("")
#define endl '\n'
#define inf mod
int n,m,root,val[N],dp[N][600],a,FT[N],ST[N],T,w[N];
vector<int>V[N];
void dfs(int x){
   ST[x] = ++T;
   w[T] = x;
   FOR(i,0,(int)V[x].size()-1)
      dfs(V[x][i]);
   FT[x] = T;
}
int main(){
   cin >> n >> m;
   FOR(i,1,n){
      scanf("%d %d",&a,&val[i]);
      if(!a) root = i;
      V[a].pb(i);
   }
   dfs(root);

   FOR(i,0,m)
      dp[n+1][i] = -inf;

   dp[n+1][0] = 0;
   
   ROF(i,n,1)
      FOR(j,0,m)
         dp[i][j] = max(dp[i+1][j] , (j!=0) * (val[w[i]] + dp[FT[w[i]]+1][j-1]));

   cout << dp[1][m] << endl;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 478308 KB Output is correct
2 Correct 0 ms 478308 KB Output is correct
3 Correct 0 ms 478308 KB Output is correct
4 Correct 9 ms 478440 KB Output is correct
5 Correct 0 ms 478308 KB Output is correct
6 Correct 6 ms 478308 KB Output is correct
7 Correct 163 ms 479364 KB Output is correct
8 Correct 135 ms 479364 KB Output is correct
9 Correct 178 ms 479232 KB Output is correct
10 Correct 255 ms 479232 KB Output is correct