Submission #715188

#	Time	Username	Problem	Language	Result	Execution time	Memory
715188		MilosMilutinovic	Biochips (IZhO12_biochips)	C++14	100 / 100	838 ms	400208 KiB

biochips

/**
 *    author:  wxhtzdy
 *    created: 26.03.2023 09:30:33
**/
#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);  
  int n, m;
  cin >> n >> m;
  vector<int> x(n);
  vector<vector<int>> g(n);
  int root;
  for (int i = 0; i < n; i++) {
    int p;
    cin >> p >> x[i];
    --p;
    if (p == -1) {
      root = i;
    } else {
      g[p].push_back(i);
      g[i].push_back(p);
    }
  }
  vector<vector<int>> dp(n, vector<int>(m + 1));
  vector<int> sz(n);
  function<void(int, int)> Dfs = [&](int v, int pv) {
    for (int u : g[v]) {
      if (u == pv) {
        continue;
      }
      Dfs(u, v);
      for (int i = min(m, sz[v]); i >= 0; i--) {
        for (int j = min(m - i, sz[u]); j >= 0; j--) {
          dp[v][i + j] = max(dp[v][i + j], dp[v][i] + dp[u][j]);          
        }
      }
      sz[v] += sz[u];
    }
    sz[v] += 1;
    dp[v][1] = max(dp[v][1], x[v]);
  };
  Dfs(root, root);
  cout << dp[root][m] << '\n';                                                               
  return 0;
}

Compilation message (stderr)

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

• Subtask 1: 100 / 100