Submission #524476

#	Time	Username	Problem	Language	Result	Execution time	Memory
524476		Pety	Biochips (IZhO12_biochips)	C++14	100 / 100	316 ms	400152 KiB

biochips

#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int INF = 1e9;
const int MOD = 1e9 + 7;

int n, m, dp[200002][502], v[200002], sz[200002];
vector<int>G[200002];

void dfs (int nod) {
  dp[nod][1] = 0;
  sz[nod] = 1;
  for (auto it : G[nod]) {
    dfs(it);
    for (int i = min(m, sz[nod]); i >= 0; i--)
      for (int j = 1; j <= min(m, sz[it]); j++)
        if (i + j <= m)
          dp[nod][i + j] = max(dp[nod][i] + dp[it][j], dp[nod][i + j]);
        else
          break;
    sz[nod] += sz[it];
  }
  dp[nod][1] = max(dp[nod][1], v[nod]);
}

int main () 
{
  ios_base::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  cin >> n >> m;
  int root;
  for (int i = 1; i <= n;i++) {
    int x, y;
    cin >>  x>> y;
    v[i] = y;
    if (x != 0)
      G[x].push_back(i);
    else
      root = i;
  }
  dfs(root);
  cout << dp[root][m];
  
  
  
  return 0;
}

Compilation message (stderr)

biochips.cpp: In function 'int main()':
biochips.cpp:44:21: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
   44 |   cout << dp[root][m];
      |                     ^

• Subtask 1: 100 / 100