Submission #884772

#	Time	Username	Problem	Language	Result	Execution time	Memory
884772		MilosMilutinovic	Worst Reporter 4 (JOI21_worst_reporter4)	C++14	79 / 100	294 ms	105996 KiB

worst_reporter2

#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  vector<int> a(n);
  vector<int> h(n);
  vector<int> c(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i] >> h[i] >> c[i];
    --a[i];
  }
  vector<vector<int>> g(n);
  vector<int> deg(n);
  for (int i = 0; i < n; i++) {
    if (a[i] != i) {
      g[a[i]].push_back(i);
    }
    deg[a[i]] += 1;
  }
  vector<int> que;
  for (int i = 0; i < n; i++) {
    if (deg[i] == 0) {
      que.push_back(i);
    }
  }
  for (int b = 0; b < (int) que.size(); b++) {
    int i = que[b];
    deg[a[i]] -= 1;
    if (deg[a[i]] == 0) {
      que.push_back(a[i]);
    }
  }
  que.emplace_back(0);
  vector<set<pair<int, long long>>> st(n);
  for (int b = 0; b < (int) que.size(); b++) {
    int i = que[b];
    int ch = -1;
    for (int j : g[i]) {
      if (ch == -1 || (int) st[ch].size() < st[j].size()) {
        ch = j;
      }
    }
    if (ch != -1) {
      st[i].swap(st[ch]);
    }
    for (int j : g[i]) {
      if (j == ch) {
        continue;
      }
      for (auto& x : st[j]) {
        int pos = x.first;
        long long val = x.second; 
        auto it = st[i].lower_bound({pos, -1LL});
        if (it != st[i].end() && it->first == pos) {
          long long old_v = it->second;
          st[i].erase(it);
          st[i].emplace(pos, old_v + val);
        } else {
          st[i].insert(x);
        }
      }
    }
    long long ft = 0;
    while (true) {
      auto it = st[i].lower_bound({h[i], -1LL});
      if (it == st[i].begin()) {
        break;
      }
      it = prev(it);
      if (it->second + ft <= c[i]) {
        ft += it->second;
        st[i].erase(it);
      } else {
        int pos = it->first;
        long long val = it->second;
        st[i].erase(it);
        st[i].emplace(pos, val + ft - c[i]);
        break;
      }
    }
    auto it = st[i].lower_bound({h[i], -1LL});
    if (it != st[i].end() && it->first == h[i]) {
      long long val = it->second;
      st[i].erase(it);
      st[i].emplace(h[i], val + c[i]);
    } else {
      st[i].emplace(h[i], c[i]);
    }
  }
  long long sum = accumulate(c.begin(), c.end(), 0LL);
  for (auto& p : st[0]) {
    sum -= p.second;
  }
  cout << sum << '\n';
  return 0;
}

Compilation message (stderr)

worst_reporter2.cpp: In function 'int main()':
worst_reporter2.cpp:44:43: warning: comparison of integer expressions of different signedness: 'int' and 'std::set<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |       if (ch == -1 || (int) st[ch].size() < st[j].size()) {
      |                       ~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~

• Subtask 1: 14 / 14
• Subtask 2: 65 / 65
• Subtask 3: 0 / 21