oj.uz

Submission #833703

# Submission time Handle Problem Language Result Execution time Memory
833703 2023-08-22T08:02:44 Z MilosMilutinovic Magic Tree (CEOI19_magictree) C++14
3 / 100
 92 ms 19064 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; 
    x[v] = d;
    y[v] = w;
  }
  vector<set<pair<int, int>>> dp(n);
  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) {
    int ch = -1;
    long long sum = 0;
    for (int u : g[v]) {
      Solve(u);
      auto it = dp[f[u]].lower_bound({x[v] + 1, -1LL});
      if (it != dp[f[u]].begin()) {
        it = prev(it);
        sum += it->first;
      }       
      if (ch == -1 || (int) dp[f[ch]].size() < (int) dp[f[u]].size()) {
        ch = u;
      }
    }
    if (ch != -1) {
      f[v] = f[ch];
    } else {
      f[v] = v;  
    }
    for (int u : g[v]) {
      if (u == ch) {
        continue;
      } else {
        for (auto& p : dp[f[u]]) {
          dp[f[v]].insert(p);
        }
        dp[f[u]].clear();
      }
    }
    Insert(v, x[v], y[v]);
  };
  Solve(0);
  long long ans = 0;
  for (auto& p : dp[f[0]]) {
    ans += p.second;
  }
  cout << ans << '\n';
  return 0;
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 12656 KB Output is correct
2 Correct 35 ms 19064 KB Output is correct
3 Correct 92 ms 17260 KB Output is correct
4 Correct 56 ms 15604 KB Output is correct
5 Correct 76 ms 17204 KB Output is correct

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 596 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 81 ms 14792 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 2388 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -