Submission #884790

#	Time	Username	Problem	Language	Result	Execution time	Memory
884790		MilosMilutinovic	Worst Reporter 4 (JOI21_worst_reporter4)	C++14	79 / 100	300 ms	105836 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);
    }
  }
  vector<set<pair<int, long long>>> st(n);
  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]);
    }
  }
  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 (int ver = 0; ver < n; ver++) {
    if (deg[ver] == 0) {
      continue;
    }
    vector<int> cyc;
    int x = ver;
    while (true) {
      cyc.push_back(x);
      x = a[x];
      if (x == ver) {
        break;
      }
    }
    vector<int> ch;
    for (int i : cyc) {
      for (int j : g[i]) {
        if (deg[j] == 0) {
          ch.push_back(j);
        }
      }
    }
    vector<pair<int, long long>> dp;
    for (int i : ch) {
      for (auto& p : st[i]) {
        dp.push_back(p);
      }
    }
    sort(dp.rbegin(), dp.rbegin());
    map<int, long long> mp;
    vector<int> f(1, -1);
    for (int i : cyc) {
      mp[h[i]] += c[i];
      f.push_back(h[i]);
    }
    sort(f.rbegin(), f.rend());
    int ptr = 0;
    long long ft = 0, mx = 0;
    for (int v : f) {
      while (ptr < (int) dp.size() && dp[ptr].first >= v) {
        ft += dp[ptr].second;
        ptr += 1;
      }
      mx = max(mx, ft + mp[v]);
    }
    sum -= mx;
    for (int i : cyc) {
      deg[i] = 0;
    }
  }
  cout << sum << '\n';
  return 0;
}

Compilation message (stderr)

worst_reporter2.cpp: In function 'int main()':
worst_reporter2.cpp:43: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]
   43 |       if (ch == -1 || (int) st[ch].size() < st[j].size()) {
      |                       ~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~

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