oj.uz

Submission #833823

# Submission time Handle Problem Language Result Execution time Memory
833823 2023-08-22T08:51:14 Z MilosMilutinovic Magic Tree (CEOI19_magictree) C++14
34 / 100
 473 ms 1048576 KB 
/**
 *    author:  wxhtzdy
 *    created: 22.08.2023 09:39:57
**/
#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);  
  int n, m, k;
  cin >> n >> m >> k;
  vector<vector<int>> g(n);
  for (int i = 1; i < n; i++) {
    int p;
    cin >> p;
    --p;
    g[p].push_back(i);
  }
  vector<int> x(n, -1), y(n);
  for (int i = 0; i < m; i++) {
    int v, d, w;
    cin >> v >> d >> w;
    --v; --d; 
    x[v] = d;
    y[v] = w;
  }
  vector<vector<long long>> dp(n, vector<long long>(k));
  /* vector<int> f(n);
   auto Insert = [&](int v, int d, int val) {
    long long s = 0;
    for (auto& p : dp[f[v]]) {
      if (p.first < d) {
        s += p.first;
        if (s > val) {
          break;
        }
      } else {
        break;
      }
    } 
    if (s <= val) {
      while (!dp[f[v]].empty() && dp[f[v]].begin()->first < d) {
        dp[f[v]].erase(dp[f[v]].begin());
      }
      dp[f[v]].emplace(d, val);
    }
  }; */
  function<void(int)> Solve = [&](int v) {
    for (int u : g[v]) {
      Solve(u);
    }         
    for (int u : g[v]) {
      for (int i = 0; i < k; i++) {
        long long mx = 0;
        for (int j = 0; j <= i; j++) {
          mx = max(mx, dp[u][j]);
        }
        dp[v][i] += mx;
      }
    }
    if (x[v] != -1) {
      dp[v][x[v]] += y[v];
    }
  };
  Solve(0);
  cout << *max_element(dp[0].begin(), dp[0].end()) << '\n';
  return 0;
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 324 KB Output is correct
2 Correct 0 ms 320 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 320 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 320 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 324 KB Output is correct

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 385 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 473 ms 8316 KB Output is correct
2 Correct 466 ms 8276 KB Output is correct
3 Correct 458 ms 8324 KB Output is correct
4 Runtime error 368 ms 1048576 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 10936 KB Output is correct
2 Correct 45 ms 12624 KB Output is correct
3 Correct 44 ms 16628 KB Output is correct
4 Correct 27 ms 11008 KB Output is correct
5 Correct 48 ms 22028 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 324 KB Output is correct
2 Correct 0 ms 320 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 320 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 320 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 324 KB Output is correct
10 Correct 74 ms 26048 KB Output is correct
11 Correct 59 ms 18116 KB Output is correct
12 Correct 69 ms 30140 KB Output is correct
13 Correct 48 ms 24524 KB Output is correct
14 Correct 56 ms 35372 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 326 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 324 KB Output is correct
2 Correct 0 ms 320 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 320 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 320 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 324 KB Output is correct
10 Correct 473 ms 8316 KB Output is correct
11 Correct 466 ms 8276 KB Output is correct
12 Correct 458 ms 8324 KB Output is correct
13 Runtime error 368 ms 1048576 KB Execution killed with signal 9
14 Halted 0 ms 0 KB -

Subtask #8
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 324 KB Output is correct
2 Correct 0 ms 320 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 320 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 320 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 324 KB Output is correct
10 Runtime error 385 ms 1048576 KB Execution killed with signal 9
11 Halted 0 ms 0 KB -