Submission #1122665

#	Time	Username	Problem	Language	Result	Execution time	Memory
1122665		xuu12312	Biochips (IZhO12_biochips)	C++20	100 / 100	601 ms	394804 KiB

biochips

#include <bits/stdc++.h>
using namespace std;

#define loop(i, a, b) for(int i = a; i <= b; i++)

vector<vector<int>> graph;
vector<vector<int>> dp;
vector<int> arr, tin, tout;
int curr_preorder = (-1);

void prep(int v) {
  tin[v] = ++curr_preorder;
  for(int s : graph[v]) {
    prep(s);
  }
  tout[v] = curr_preorder;
}

int n, m;

void solve(int v) {
  dp[tin[v]][0] = 0;
  dp[tin[v] + 1][m] = max(dp[tin[v] + 1][m], dp[tin[v]][m]);
  loop(i, 0, m-1) {
    dp[tout[v] + 1][i + 1] = max(dp[tout[v] + 1][i + 1], dp[tin[v]][i] + arr[v]);
    dp[tin[v] + 1][i] = max(dp[tin[v] + 1][i], dp[tin[v]][i]);
  }
  for(int s : graph[v]) {
    solve(s);
  }
}

int main() {
  cin.tie(0)->sync_with_stdio(false);
  cin >> n >> m;

  dp.resize(n + 1, vector<int>(m + 1, (-1e9)));
  graph.resize(n + 1);
  tout.resize(n + 1);
  tin.resize(n + 1);
  arr.resize(n + 1);

  int root;

  loop(i, 1, n) {
    int p; cin >> p >> arr[i];
    if(p == 0) root = i;
    else graph[p].push_back(i);
  }

  prep(root);
  solve(root);

  cout << dp[n][m] << '\n';

}

• Subtask 1: 100 / 100