Submission #834060

#	Time	Username	Problem	Language	Result	Execution time	Memory
834060		MilosMilutinovic	Magic Tree (CEOI19_magictree)	C++14	100 / 100	121 ms	34428 KiB

magictree

/**
 *    author:  wxhtzdy
 *    created: 22.08.2023 12:12:51
**/
#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, long long>>> dp(n);
  function<void(int)> Dfs = [&](int v) {
    int ch = -1;
    for (int u : g[v]) {
      Dfs(u);
      if (ch == -1 || (int) dp[u].size() > (int) dp[ch].size()) {
        ch = u;
      }
    }     
    if (ch != -1) {
      swap(dp[v], dp[ch]);
    }
    for (int u : g[v]) {
      if (u == ch) {
        continue;
      }            
      for (auto& p : dp[u]) {
        auto it = dp[v].lower_bound({p.first, -1LL});
        if (it != dp[v].end() && it->first == p.first) {
          int fir = it->first;
          long long sec = it->second;
          dp[v].erase(it);
          dp[v].emplace(fir, sec + p.second);                    
        } else {
          dp[v].insert(p);
        }
      }
    }
    if (x[v] != -1) {
      auto it = dp[v].lower_bound({x[v], -1LL});
      if (it != dp[v].end() && it->first == x[v]) {
        int fir = it->first;
        long long sec = it->second;
        dp[v].erase(it);
        dp[v].emplace(fir, sec + y[v]);
      } else {
        dp[v].emplace(x[v], y[v]); 
      }
      long long s = 0;
      while (true) {
        auto it = dp[v].lower_bound({x[v] + 1, -1LL});
        if (it == dp[v].end()) {
          break;
        }
        if (s + it->second <= y[v]) {
          s += it->second;
          dp[v].erase(it);
        } else {
          int fir = it->first;
          long long sec = it->second;
          dp[v].erase(it);
          dp[v].emplace(fir, sec - (y[v] - s));
          break;
        }
      }
    }
  };
  Dfs(0);
  long long ans = 0;
  for (auto& p : dp[0]) {
    ans += p.second;
  }
  cout << ans << '\n';                
  return 0;
}

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