Submission #681078

#	Time	Username	Problem	Language	Result	Execution time	Memory
681078		peijar	Magic Tree (CEOI19_magictree)	C++17	100 / 100	158 ms	18396 KiB

magictree

#include <bits/stdc++.h>
#define int long long
using namespace std;

namespace std {
template <typename T> ostream &operator<<(ostream &out, const vector<T> &vec) {
  out << "[";
  for (int i = 0; i < (int)vec.size(); ++i) {
    out << vec[i];
    if (i + 1 < (int)vec.size())
      out << ", ";
  }
  return out << "]";
}
} // namespace std

void dbg_out() { cout << endl; }
template <typename Head, typename... Tail> void dbg_out(Head H, Tail... T) {
  cout << ' ' << H;
  dbg_out(T...);
}

#ifdef DEBUG
#define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif

signed main(void) {
  ios_base::sync_with_stdio(false);
  cin.tie(0);

  int nbSommet, nbFruits, nbJours;
  cin >> nbSommet >> nbFruits >> nbJours;
  vector<vector<int>> childs(nbSommet);

  for (int i = 1; i < nbSommet; ++i) {
    int p;
    cin >> p;
    childs[p - 1].push_back(i);
  }
  vector<pair<int, int>> fruits(nbSommet, pair(-1, -1));
  for (int i = 0; i < nbFruits; ++i) {
    int v, d, w;
    cin >> v >> d >> w;
    --v;
    fruits[v] = pair(d - 1, w);
  }

  vector<map<int, int>> changements(nbSommet);

  for (int u = nbSommet - 1; u >= 0; --u) {
    for (int v : childs[u]) {
      if (changements[v].size() > changements[u].size())
        changements[u].swap(changements[v]);
      for (auto [x, delta] : changements[v])
        changements[u][x] += delta;
      changements[v].clear();
    }
    if (fruits[u].first == -1)
      continue;
    auto [d, w] = fruits[u];
    int curDel = 0;
    int lstDel = -1;
    while (true) {
      auto it = changements[u].upper_bound(d);
      if (it == changements[u].end())
        break;
      curDel += it->second;
      if (curDel <= w) {
        changements[u].erase(it);
      } else {
        changements[u][it->first] = curDel - w;
        break;
      }
    }
    changements[u][d] += w;
  }
  int sol = 0;
  for (auto [x, delta] : changements[0])
    sol += delta;
  cout << sol << endl;
}

Compilation message (stderr)

magictree.cpp: In function 'int main()':
magictree.cpp:64:9: warning: unused variable 'lstDel' [-Wunused-variable]
   64 |     int lstDel = -1;
      |         ^~~~~~

• 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