제출 #884796

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
884796		MilosMilutinovic	Worst Reporter 4 (JOI21_worst_reporter4)	C++14	100 / 100	295 ms	104024 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++) {
    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]);
    }
  }
  vector<bool> was(n);
  for (int i : que) {
    was[i] = true;
  }
  long long sum = accumulate(c.begin(), c.end(), 0LL);
  for (int ver = 0; ver < n; ver++) {
    if (was[ver]) {
      continue;
    }
    vector<int> cyc;
    int x = ver;
    while (!was[x]) {
      was[x] = true;
      cyc.push_back(x);
      x = a[x];
    }
    vector<int> ch;
    for (int i : cyc) {
      for (int j : g[i]) {
        if (deg[j] == 0) {
          ch.push_back(j);
        }
      }
    }
    sort(ch.begin(), ch.end());
    ch.erase(unique(ch.begin(), ch.end()), ch.end());
    vector<pair<int, long long>> dp;
    for (int i : ch) {
      assert(!st[i].empty());
      for (auto& p : st[i]) {
        dp.push_back(p);
      }
    }
    sort(dp.rbegin(), dp.rend());
    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());
    f.erase(unique(f.begin(), f.end()), f.end());
    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;
  }
  cout << sum << '\n';
  return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

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

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