Submission #788623

#	Time	Username	Problem	Language	Result	Execution time	Memory
788623		WLZ	Magic Tree (CEOI19_magictree)	C++17	100 / 100	112 ms	37684 KiB

magictree

#include <bits/stdc++.h>
using namespace std;
 
vector< vector<int> > g;
vector<int> d;
vector<long long> w;
vector< map<long long, long long> > dp;
 
void dfs(int u) {
  for (auto& v : g[u]) {
    dfs(v);
    if ((int) dp[u].size() < (int) dp[v].size()) {
      swap(dp[u], dp[v]);
    }
    for (auto& p : dp[v]) {
      dp[u][p.first] += p.second;
    }
  }
  dp[u][d[u]] += w[u];
  auto it = dp[u].upper_bound(d[u]);
  long long tmp = w[u];
  while (it != dp[u].end()) {
    if (it->second > tmp) {
      it->second -= tmp;
      break;
    }
    tmp -= it->second;
    dp[u].erase(it++);
  }
}
 
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, m, k;
  cin >> n >> m >> k;
  g.resize(n + 1);
  for (int i = 2; i <= n; i++) {
    int p;
    cin >> p;
    g[p].push_back(i);
  }
  d.assign(n + 1, 1);
  w.resize(n + 1);
  for (int i = 0; i < m; i++) {
    int v;
    cin >> v;
    cin >> d[v] >> w[v];
  }
  dp.resize(n + 1);
  dfs(1);
  long long ans = 0;
  for (auto& p : dp[1]) {
    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