Submission #392329

#	Time	Username	Problem	Language	Result	Execution time	Memory
392329		MiricaMatei	Worst Reporter 4 (JOI21_worst_reporter4)	C++14	100 / 100	452 ms	77156 KiB

worst_reporter2

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 200005;
const int inf = 2000000000;
const long long INF = 1000000000000000000LL;

struct slope_trick {
  map<int, long long> delta;

  slope_trick () {
    delta = map<int, long long>();
  }

  void mergeDelta(slope_trick other) {
    for (auto it:other.delta)
      delta[it.first] += it.second;
    other.delta.clear();
  }

  void add(int x, long long val) {
    delta[-inf] += val;
    delta[x] -= val;
    delta[x + 1] += val;
  }

  void level(int x) {
    map<int, long long>::iterator it1, it2;
    it1 = delta.lower_bound(x);

    long long val = delta[x];
    while (val < 0) {
      it2 = it1;
      it1--;
      delta.erase(it2);
      val = it1->second + val;
      it1->second = val;
    }
  }

  int mapSize() {
    return delta.size();
  }

  long long query() {
    return delta[-inf];
  }
};

vector<int>G[MAXN];

int a[MAXN], h[MAXN], c[MAXN];
bool vis[MAXN], visc[MAXN];

slope_trick dfs(int node) {
  slope_trick ans;
  vis[node] = 1;
  for (auto it:G[node]) {
    slope_trick aux = dfs(it);
    if (aux.mapSize() > ans.mapSize())
      swap(ans, aux);
    ans.mergeDelta(aux);
  }
  ans.add(h[node], c[node]);
  ans.level(h[node]);
  return ans;
}

long long solve(int node) {
  vector<int>cycle;
  while (!vis[node]) {
    vis[node] = 1;
    node = a[node];
  }
  while (!visc[node]) {
    cycle.push_back(node);
    visc[node] = 1;
    node = a[node];
  }

  slope_trick ans;
  for (auto it:cycle)
    for (auto son:G[it])
      if (!visc[son]) {
        slope_trick aux = dfs(son);
        if (aux.mapSize() > ans.mapSize())
          swap(ans, aux);
        ans.mergeDelta(aux);
      }

  for (auto it:cycle) {
    vis[it] = 1;
    ans.add(h[it], c[it]);
  }

  long long sol = INF;
  long long s = 0;
  for (auto it:ans.delta) {
    s += it.second;
    sol = min(sol, s);
  }

  return sol;
}

int main() {
  //freopen("date.in", "r", stdin);
  //freopen("date.out", "w", stdout);

  int N;
  scanf("%d", &N);
  for (int i = 1; i <= N; ++i) {
    scanf("%d%d%d", &a[i], &h[i], &c[i]);
    G[a[i]].push_back(i);
  }

  long long ans = 0;
  for (int i = 1; i <= N; ++i)
    if (!vis[i])
      ans += solve(i);

  printf("%lld\n", ans);

  return 0;
}

Compilation message (stderr)

worst_reporter2.cpp: In function 'int main()':
worst_reporter2.cpp:112:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  112 |   scanf("%d", &N);
      |   ~~~~~^~~~~~~~~~
worst_reporter2.cpp:114:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  114 |     scanf("%d%d%d", &a[i], &h[i], &c[i]);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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