Submission #789366

#	Time	Username	Problem	Language	Result	Execution time	Memory
789366		peijar	Worst Reporter 4 (JOI21_worst_reporter4)	C++17	100 / 100	390 ms	116856 KiB

worst_reporter2

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

string to_string(string s) { return s; }
template <typename T> string to_string(T v) {
  bool first = true;
  string res = "[";
  for (const auto &x : v) {
    if (!first)
      res += ", ";
    first = false;
    res += to_string(x);
  }
  res += "]";
  return res;
}

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

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

const int MAXN = 2e5;

vector<int> childs[MAXN];
int par[MAXN];
int health[MAXN];
int cost[MAXN];
bool inCycle[MAXN];
vector<vector<int>> cycles;
int sz[MAXN];
int sumCost[MAXN];
map<int, int> deltas[MAXN];

void solve(int u) {
  sumCost[u] = cost[u];
  for (int v : childs[u])
    if (!inCycle[v]) {
      solve(v);
      sz[u] += sz[v];
      sumCost[u] += sumCost[v];
      if (deltas[u].size() < deltas[v].size())
        deltas[u].swap(deltas[v]);
      for (auto [x, d] : deltas[v])
        deltas[u][x] += d;
    }

  deltas[u][health[u]] += cost[u];

  int toRem = cost[u];
  while (toRem > 0) {
    auto it = deltas[u].lower_bound(health[u]);
    if (it == deltas[u].begin())
      break;
    --it;
    int rem = min(toRem, it->second);
    toRem -= rem;
    it->second -= rem;
    if (it->second == 0)
      deltas[u].erase(it);
  }
}

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

  int nbPersonnes;
  cin >> nbPersonnes;
  vector<int> values;
  for (int i = 0; i < nbPersonnes; ++i) {
    cin >> par[i] >> health[i] >> cost[i];
    --par[i];
    childs[par[i]].push_back(i);
    values.push_back(health[i]);
  }
  sort(values.begin(), values.end());
  values.resize(unique(values.begin(), values.end()) - values.begin());
  for (int i = 0; i < nbPersonnes; ++i) {
    health[i] =
        lower_bound(values.begin(), values.end(), health[i]) - values.begin();
  }

  vector<int> visited(nbPersonnes, 0);

  for (int u = 0; u < nbPersonnes; ++u)
    if (not visited[u]) {
      vector<int> stk;
      int v = u;
      while (!visited[v]) {
        stk.push_back(v);
        visited[v] = 1;
        v = par[v];
      }
      if (visited[v] == 1) {
        vector<int> c;
        while (stk.back() != v) {
          c.push_back(stk.back());
          stk.pop_back();
        }
        c.push_back(stk.back());
        stk.pop_back();
        cycles.push_back(c);
        for (int x : c)
          inCycle[x] = true, visited[x] = 2;
      }
      for (int x : stk)
        visited[x] = 2;
    }
  dbg(cycles);

  int sol = 0;
  for (auto cyc : cycles) {
    map<int, int> deltaCycle;
    for (int root : cyc)
      for (int u : childs[root])
        if (!inCycle[u]) {
          solve(u);
          if (deltaCycle.size() < deltas[u].size())
            deltaCycle.swap(deltas[u]);
          for (auto [x, d] : deltas[u])
            deltaCycle[x] += d;
        }
    for (auto it = deltaCycle.rbegin(); it != deltaCycle.rend(); ++it)
      if (it != deltaCycle.rbegin())
        it->second += prev(it)->second;
    map<int, int> withH;
    int costCycle = 0;
    for (int root : cyc)
      withH[health[root]] += cost[root], costCycle += cost[root];
    for (int root : cyc)
      for (int u : childs[root])
        if (!inCycle[u])
          costCycle += sumCost[u];
    int cur = 1e18;
    for (auto [x, d] : deltaCycle) {
      cur = min(cur, costCycle - withH[x]);
    }
    for (auto [h, c] : withH) {
      auto it = deltaCycle.lower_bound(h);
      int curCost = costCycle - c;
      if (it != deltaCycle.end())
        curCost -= it->second;
      cur = min(cur, curCost);
    }
    sol += cur;
  }
  cout << sol << endl;
}

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