Submission #1282451

#	Time	Username	Problem	Language	Result	Execution time	Memory
1282451		lmquan	Magic Tree (CEOI19_magictree)	C++20	0 / 100	2096 ms	34536 KiB

magictree

#define taskname ""
#include <bits/stdc++.h>
using namespace std;

int main() {
  if (fopen(taskname".inp", "r")) {
    freopen(taskname".inp", "r", stdin);
    freopen(taskname".out", "w", stdout);
  }
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  int n, m, k;
  cin >> n >> m >> k;

  vector<vector<int>> children(n + 1);
  for (int i = 2; i <= n; i++) {
    int p;
    cin >> p;
    children[p].push_back(i);
  }
  vector<pair<int, int>> q(n + 1, {-1, -1});
  vector<int> s;
  for (int i = 1; i <= m; i++) {
    int v, d, w;
    cin >> v >> d >> w;
    q[v] = {d, w};
    s.push_back(d);
  }
  sort(s.begin(), s.end());
  s.erase(unique(s.begin(), s.end()), s.end());
  for (int i = 1; i <= n; i++) {
    if (q[i].first != -1) {
      q[i].first = upper_bound(s.begin(), s.end(), q[i].first) - s.begin();
    }
  }

  vector<set<pair<int, long long>>> d(n + 1);

  function<void(int)> DFS = [&](int u) {
    for (int v : children[u]) {
      DFS(v);
      if (d[u].size() < d[v].size()) {
        swap(d[u], d[v]);
      }
      for (auto i : d[v]) {
        auto it = d[u].lower_bound({i.first, 0});
        if (it == d[u].end() || (*it).first > i.first) {
          d[u].insert(i);
        } else {
          d[u].insert({it->first, it->second + i.second});
          d[u].erase(it);
        }
      }
      d[v].clear();
    }

    if (q[u].first != -1) {
      while (d[u].size() < q[u].first) {
        d[u].insert({(d[u].empty() ? 0 : (--d[u].end())->first + 1), 0});
      }
      auto it = d[u].lower_bound({q[u].first - 1, 0});
      d[u].insert({it->first, it->second + q[u].second});
      it = d[u].erase(it);
      it++;
      long long t = -q[u].second;
      while (true) {
        if (it == d[u].end()) {
          break;
        }
        pair<int, long long> x = *it;
        x.second += t;
        it = d[u].erase(it);
        if (x.second >= 0) {
          d[u].insert(x);
          break;
        }
        t = x.second, x.second = 0;
        d[u].insert(x);
      }
    }
  };

  int root = 1;
  DFS(root);

  long long result = 0;
  for (auto i : d[root]) {
    result += i.second;
  }
  cout << result;

  return 0;
}

Compilation message (stderr)

magictree.cpp: In function 'int main()':
magictree.cpp:7:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    7 |     freopen(taskname".inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
magictree.cpp:8:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    8 |     freopen(taskname".out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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