Submission #1039980

#	Time	Username	Problem	Language	Result	Execution time	Memory
1039980		juicy	Worst Reporter 4 (JOI21_worst_reporter4)	C++17	100 / 100	214 ms	104720 KiB

worst_reporter2

#include <bits/stdc++.h>

using namespace std;

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

const int N = 2e5 + 5;

int n;
int nxt[N], a[N], c[N], lab[N], deg[N];
vector<int> g[N];
map<int, long long> mp[N];

void mrg(map<int, long long> &a, map<int, long long> &b) {
  if (a.size() < b.size()) {
    swap(a, b);
  }
  for (auto [x, y] : b) {
    a[x] += y;
  }
}

void opt(map<int, long long> &mp, int x, long long C) {
  mp[x] += C;
  for (auto it = mp.upper_bound(x); it != mp.end(); it = mp.erase(it)) {
    auto &delta = (*it).second;
    if (C < delta) {
      delta -= C;
      break;
    }
    C -= delta;
  }
}

void dfs(int u) {
  for (int v : g[u]) {
    dfs(v);
    mrg(mp[u], mp[v]);
  }
  opt(mp[u], a[u], c[u]);
}

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

  cin >> n;
  long long res = 0;
  for (int i = 1; i <= n; ++i) {
    int p; cin >> p >> a[i] >> c[i];
    a[i] = 1e9 - a[i] + 1;
    res += c[i];
    g[p].push_back(i);
    nxt[i] = p, ++deg[p];
  }
  queue<int> q;
  for (int i = 1; i <= n; ++i) {
    if (!deg[i]) {
      q.push(i);
    }
  }
  while (q.size()) {
    int u = q.front(); q.pop();
    if (--deg[nxt[u]] == 0) {
      q.push(nxt[u]);
    }
  }
  for (int i = 1; i <= n; ++i) {
    if (deg[i]) {
      int j = i;
      vector<int> cands;
      do {
        cands.push_back(j);
        for (int v : g[j]) {
          if (!deg[v]) {
            dfs(v);
            mrg(mp[i], mp[v]);
          }
        }
        j = nxt[j];
      } while (j ^ i);
      sort(cands.begin(), cands.end(), [&](int u, int v) {
        return a[u] > a[v];
      });
      for (int it = 0; it < cands.size(); ) {
        int j = it;
        long long sum = 0;
        while (j < cands.size() && a[cands[j]] == a[cands[it]]) {
          deg[cands[j]] = 0;
          sum += c[cands[j++]];
        }
        opt(mp[i], a[cands[it]], sum);
        it = j;
      }
      for (auto [x, y] : mp[i]) {
        res -= y;
      }
    }
  }
  cout << res;
  return 0;
}

Compilation message (stderr)

worst_reporter2.cpp: In function 'int main()':
worst_reporter2.cpp:88:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |       for (int it = 0; it < cands.size(); ) {
      |                        ~~~^~~~~~~~~~~~~~
worst_reporter2.cpp:91:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |         while (j < cands.size() && a[cands[j]] == a[cands[it]]) {
      |                ~~^~~~~~~~~~~~~~

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