oj.uz

Submission #992582

# Submission time Handle Problem Language Result Execution time Memory
992582 2024-06-04T17:50:55 Z tch1cherin Biochips (IZhO12_biochips) C++17
100 / 100
 496 ms 395600 KB 
#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 200000;
vector<int> graph[MAX_N];
int W[MAX_N];
int tin[MAX_N], tout[MAX_N], pos[MAX_N];
int cur = 0;

void dfs(int u) {
  tin[u] = cur;
  pos[cur++] = u;
  for (int v : graph[u]) {
    dfs(v);
  }
  tout[u] = cur;
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int N, M;
  cin >> N >> M;
  int root = -1;
  for (int i = 0; i < N; i++) {
    int p;
    cin >> p >> W[i];
    p--;
    if (p != -1) {
      graph[p].push_back(i);
    } else {
      root = i;
    }
  }
  dfs(root);
  vector<vector<int>> dp(N + 1, vector<int>(M + 1, -1e9));
  for (int i = 0; i <= N; i++) {
    dp[i][0] = 0;
  }
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < M; j++) {
      dp[tout[pos[i]]][j + 1] = max(dp[tout[pos[i]]][j + 1], dp[i][j] + W[pos[i]]);
    }
    for (int j = 0; j <= M; j++) {
      dp[i + 1][j] = max(dp[i + 1][j], dp[i][j]);
    }
  }
  cout << dp[N][M] << "\n";
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8028 KB Output is correct
2 Correct 2 ms 8108 KB Output is correct
3 Correct 2 ms 8028 KB Output is correct
4 Correct 7 ms 10588 KB Output is correct
5 Correct 7 ms 11608 KB Output is correct
6 Correct 12 ms 12636 KB Output is correct
7 Correct 237 ms 189644 KB Output is correct
8 Correct 270 ms 189784 KB Output is correct
9 Correct 347 ms 293776 KB Output is correct
10 Correct 496 ms 395600 KB Output is correct