Submission #386381

#	Time	Username	Problem	Language	Result	Execution time	Memory
386381		Mamnoon_Siam	Worst Reporter 4 (JOI21_worst_reporter4)	C++17	100 / 100	643 ms	100256 KiB

worst_reporter2

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

using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
using pil = pair<int, ll>;
#define all(v) begin(v), end(v)
#define sz(v) (int)(v).size()
#define fi first
#define se second

const int N = 2e5 + 5;
const int lg = 18;

vi g[N];
int n;
int A[N], H[N];
ll C[N];
vector<pil> mem[N];
int sub[N];

namespace bit {
  int edits[4*lg*N], ptr = 0;
  ll ft[N];
  void clear() {
    while(ptr)
      ft[edits[--ptr]] = 0;
  }
  void update(int l, int r, ll x) {
    for(; l <= n; l += l & -l) {
      ft[l] += x;
      edits[ptr++] = l;
    }
    for(r++; r <= n; r += r & -r) {
      ft[r] -= x;
      edits[ptr++] = r;
    }
  }
  ll query(int pos) {
    ll ret = 0;
    for(; pos > 0; pos -= pos & -pos)
      ret += ft[pos];
    return ret;
  }
  int func(int r, ll x) { // max l < r such that query(l) < x
    int idx = 0; ll sm = 0;
    for(int pw = 1 << (lg-1); pw; pw >>= 1) {
      if((idx|pw) < r and sm + ft[idx|pw] < x) {
        idx |= pw;
        sm += ft[idx];
      }
    }
    return idx;
  }
  vector<pil> grab() {
    std::vector<pil> ret;
    int l = 1;
    while(l <= n) {
      ll x = query(l);
      int r = func(n+1, x+1);
      ret.emplace_back(l, x);
      l = r+1;
    }
    ret.emplace_back(n+1, 69); // hehe
    return ret;
  }
}

void solve(int u, bool keep) {
  ii big;
  for(int v : g[u])
    big = max(big, ii(sub[v], v));

  for(int v : g[u])
    if(v != big.se) solve(v, 0);
  if(big.se) solve(big.se, 1);

  for(int v : g[u]) if(v != big.se) {
    vector<pil>& f = mem[v];
    for(int i = 0; i < sz(f)-1; ++i) {
      bit::update(f[i].fi, f[i+1].fi-1, f[i].se);
    }
  }

  ll val = bit::query(H[u]);

  bit::update(1, n, C[u]);

  int r = H[u];
  for(ll val_r = bit::query(r); val_r > val; val_r = bit::query(r)) {
    int l = bit::func(r, val_r);
    ll x = val_r - val;
    bit::update(l+1, r, -x);
    r = l;
  }

  if(!keep) {
    mem[u] = bit::grab();
    bit::clear();
  }
}

int vis[N], onstk[N], par[N];
set<ii> edges;
vector<vi> cyc;

void dfs(int u) {
  vis[u] = onstk[u] = 1;

  for(int v : {A[u]}) {
    if(vis[v]) {
      if(onstk[v]) {
        cyc.push_back({});
        vi &bk = cyc.back();
        int uu = u;
        bk.emplace_back(uu);
        while(uu != v) {
          uu = par[uu];
          bk.emplace_back(uu);
        }
        // reverse(all(bk));
      }
    } else {
      par[v] = u;
      dfs(v);
    }
  }

  onstk[u] = 0;
}

void dfs_init(int u) {
  sub[u] = 1;
  for(int v : g[u]) {
    dfs_init(v);
    sub[u] += sub[v];
  }
}

int main(int argc, char const *argv[])
{
#ifdef LOCAL
  freopen("in", "r", stdin);
#endif
  scanf("%d", &n);
  for(int i = 1; i <= n; ++i) {
    scanf("%d %d %lld", &A[i], &H[i], &C[i]);
  }
  { // compress
    vi tmp(H+1, H+1+n);
    sort(all(tmp));
    tmp.erase(unique(all(tmp)), tmp.end());
    for(int i = 1; i <= n; ++i)
      H[i] = int(lower_bound(all(tmp), H[i]) - tmp.begin()) + 1;
  }

  for(int i = 1; i <= n; ++i) {
    if(!vis[i]) {
      dfs(i);
    }
  }

  for(vi& c : cyc) for(int u : c) A[u] = -1;

  for(int i = 1; i <= n; ++i)
    if(~A[i]) g[A[i]].emplace_back(i);

  ll ans = 0;

  vector<ll> sm(n+1);

  for(vi &c : cyc) {
    vi ls;
    ll tot = 0;
    for(int u : c) {
      ls.insert(ls.end(), all(g[u]));
      tot += C[u];
      sm[H[u]] += C[u];
    }
    for(int v : ls) {
      dfs_init(v);
      solve(v, 0);
    }

    for(int v : ls) {
      vector<pil>& f = mem[v];
      for(int i = 0; i < sz(f)-1; ++i) {
        bit::update(f[i].fi, f[i+1].fi-1, f[i].se);
      }
    }

    ll now = LLONG_MAX;
    for(int u : c) {
      int x = H[u];
      now = min(now, tot - sm[x] + bit::query(x));
    }
    now = min(now, tot - sm[1] + bit::query(1));

    ans += now;

    bit::clear();

    for(int u : c) sm[H[u]] -= C[u];
  }
  printf("%lld\n", ans);
  return 0;
}

Compilation message (stderr)

worst_reporter2.cpp: In function 'int main(int, const char**)':
worst_reporter2.cpp:146:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  146 |   scanf("%d", &n);
      |   ~~~~~^~~~~~~~~~
worst_reporter2.cpp:148:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  148 |     scanf("%d %d %lld", &A[i], &H[i], &C[i]);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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