Submission #789351

#	Time	Username	Problem	Language	Result	Execution time	Memory
789351		peijar	Worst Reporter 4 (JOI21_worst_reporter4)	C++17	79 / 100	328 ms	112256 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) {
    for (int root : cyc)
      solve(root);
    int tailleCycle = cyc.size();
    for (int root : cyc)
      for (auto it = deltas[root].rbegin(); it != deltas[root].rend(); ++it)
        if (it != deltas[root].rbegin())
          it->second += prev(it)->second;
    int cur = 0;
    for (int root : cyc) {
      cur += sumCost[root];
      cur -= deltas[root].begin()->second;
    }
    sol += cur;
  }
  cout << sol << endl;
}

Compilation message (stderr)

worst_reporter2.cpp: In function 'int main()':
worst_reporter2.cpp:124:9: warning: unused variable 'tailleCycle' [-Wunused-variable]
  124 |     int tailleCycle = cyc.size();
      |         ^~~~~~~~~~~

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