Submission #833829

#	Time	Username	Problem	Language	Result	Execution time	Memory
833829		MilosMilutinovic	Magic Tree (CEOI19_magictree)	C++14	47 / 100	2097 ms	1048576 KiB

magictree

/**
 *    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<vector<long long>> dp(n);
  vector<vector<int>> days(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) {
    for (int u : g[v]) {
      Solve(u);
      for (int x : days[u]) {
        days[v].push_back(x);
      }
    }         
    if (x[v] != -1) {
      days[v].push_back(x[v]);
    }
    sort(days[v].begin(), days[v].end());
    days[v].erase(unique(days[v].begin(), days[v].end()), days[v].end());
    int sz = (int) days[v].size();
    dp[v].resize(sz);
    for (int u : g[v]) {
      long long mx = 0;
      int ptr = 0;
      for (int j = 0; j < sz; j++) {
        while (ptr < (int) days[u].size() && days[v][j] >= days[u][ptr]) {
          mx = max(mx, dp[u][ptr]);
          ptr += 1;
        }
        dp[v][j] += mx;
      }
    } 
    if (x[v] != -1) {
      for (int i = 0; i < sz; i++) {
        if (days[v][i] == x[v]) {
          dp[v][i] += y[v];
          break;
        }
      }
    }
  };
  Solve(0);
  cout << *max_element(dp[0].begin(), dp[0].end()) << '\n';
  return 0;
}

• Subtask 1: 6 / 6
• Subtask 2: 0 / 3
• Subtask 3: 0 / 11
• Subtask 4: 12 / 12
• Subtask 5: 16 / 16
• Subtask 6: 13 / 13
• Subtask 7: 0 / 22
• Subtask 8: 0 / 17