oj.uz

Submission #715188

# Submission time Handle Problem Language Result Execution time Memory
715188 2023-03-26T07:39:22 Z MilosMilutinovic Biochips (IZhO12_biochips) C++14
100 / 100
 838 ms 400208 KB 
/**
 *    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

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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 320 KB Output is correct
4 Correct 5 ms 3412 KB Output is correct
5 Correct 6 ms 4424 KB Output is correct
6 Correct 8 ms 5324 KB Output is correct
7 Correct 320 ms 191020 KB Output is correct
8 Correct 299 ms 191012 KB Output is correct
9 Correct 628 ms 297364 KB Output is correct
10 Correct 838 ms 400208 KB Output is correct