Submission #1086539

#	Time	Username	Problem	Language	Result	Execution time	Memory
1086539		juicy	Magic Tree (CEOI19_magictree)	C++17	100 / 100	115 ms	37308 KiB

magictree

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

const int N = 1e5 + 5;

int n, m, k;
int a[N], c[N];
vector<int> g[N];
map<int, long long> mp[N];

void dfs(int u) {
  for (auto v : g[u]) {
    dfs(v);
    if (mp[u].size() < mp[v].size()) {
      mp[u].swap(mp[v]);
    }
    for (auto [x, y] : mp[v]) {
      mp[u][x] += y;
    }
  }
  mp[u][a[u]] += c[u];
  for (auto it = mp[u].upper_bound(a[u]); it != mp[u].end(); it = mp[u].erase(it)) {
    auto &cnt = (*it).second;
    long long k = min(cnt, (long long) c[u]);
    c[u] -= k;
    cnt -= k;
    if (cnt) {
      break;
    }
  }
}

int main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);

  cin >> n >> m >> k;
  for (int i = 2; i <= n; ++i) {
    int p; cin >> p;
    g[p].push_back(i);
  }
  while (m--) {
    int v, d, w; cin >> v >> d >> w;
    tie(a[v], c[v]) = tie(d, w);
  }
  dfs(1);
  long long res = 0;
  for (auto x : mp[1]) {
    res += x.second;
  }
  cout << res;
  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