Submission #1239846

#	Time	Username	Problem	Language	Result	Execution time	Memory
1239846		rxlfd314	Tree (IOI24_tree)	C++20	31 / 100	2097 ms	45728 KiB

tree

#include "tree.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ari2 = array<int, 2>;
using ari3 = array<int, 3>;
using arl2 = array<ll, 2>;
using arl3 = array<ll, 3>;
template <class T> using vt = vector<T>;
#define all(x) begin(x), end(x)
#define size(x) (int((x).size()))
#define REP(a,b,c,d) for(int a=(b);(d)>0?a<=(c):a>=(c);a+=(d))
#define FOR(a,b,c) REP(a,b,c,1)
#define ROF(a,b,c) REP(a,b,c,-1)

constexpr int mxN = 200005;
int N;
vt<int> P, W, adj[mxN];
int hson[mxN], szs[mxN];
int tin[mxN], tout[mxN], head[mxN], timer, rev_tin[mxN];

struct Node {
  ll mss;
  ari2 min_w;
  ll lz;
  Node operator+(const Node &other) {
    return {min(mss, other.mss), min(min_w, other.min_w), 0};
  }
} st[mxN<<2];
#define lc i << 1
#define rc lc | 1
void build(const int i = 1, const int tl = 0, const int tr = N-1) {
  if (tl == tr)
    st[i] = {LLONG_MAX, ari2{W[rev_tin[tl]], rev_tin[tl]}, 0};
  else {
    const int tm = tl + tr >> 1;
    build(lc, tl, tm);
    build(rc, tm+1, tr);
    st[i] = st[lc] + st[rc];
  }
}
void app(const int i, const ll lz) {
  st[i].mss += lz;
  st[i].lz += lz;
}
void push(const int i) {
  if (st[i].lz == 0)
    return;
  app(lc, st[i].lz);
  app(rc, st[i].lz);
  st[i].lz = 0;
}
void update_add(const int ql, const int qr, const ll v, const int i = 1, const int tl = 0, const int tr = N-1) {
  if (tl > qr || tr < ql)
    return;
  if (ql <= tl && tr <= qr)
    app(i, v);
  else {
    push(i);
    const int tm = tl + tr >> 1;
    update_add(ql, qr, v, lc, tl, tm);
    update_add(ql, qr, v, rc, tm+1, tr);
    st[i] = st[lc] + st[rc];
  }
}
void update_set(const int p, const int i = 1, const int tl = 0, const int tr = N-1) {
  if (tl == tr)
    st[i].min_w = {INT_MAX, -1};
  else {
    push(i);
    const int tm = tl + tr >> 1;
    if (p <= tm)
      update_set(p, lc, tl, tm);
    else
      update_set(p, rc, tm+1, tr);
    st[i] = st[lc] + st[rc];
  }
}
void update_mss(const int p, const ll v, const int i = 1, const int tl = 0, const int tr = N-1) {
  if (tl == tr)
    st[i].mss = v;
  else {
    push(i);
    const int tm = tl + tr >> 1;
    if (p <= tm)
      update_mss(p, v, lc, tl, tm);
    else
      update_mss(p, v, rc, tm+1, tr);
    st[i] = st[lc] + st[rc];
  }
}
Node query_path(const int ql, const int qr, const int i = 1, const int tl = 0, const int tr = N-1) {
  if (tl > qr || tr < ql)
    return {LLONG_MAX, ari2{INT_MAX, -1}, LLONG_MAX};
  if (ql <= tl && tr <= qr)
    return st[i];
  push(i);
  const int tm = tl + tr >> 1;
  return query_path(ql, qr, lc, tl, tm) + query_path(ql, qr, rc, tm+1, tr);
}
#undef lc
#undef rc
ll worst(int i) {
  ll ret = LLONG_MAX;
  for (; i >= 0; i = P[head[i]])
    ret = min(ret, query_path(tin[head[i]], tin[i]).mss);
  return ret;
}
void update_path(int i, const ll v) {
  for (; i >= 0; i = P[head[i]])
    update_add(tin[head[i]], tin[i], v);
} 
ll query(int L, int R) {
  ll ans = 0;
  build();
  const auto dfs = [&](auto &&self, const int i) -> int {
    if (tin[i] == tout[i]) {
      ans += 1ll * L * W[i];
      update_set(tin[i]);
      return L;
    }
    ll cur_sum = 0;
    for (const auto &j : adj[i])
      cur_sum += self(self, j);
    //cout << worst(0) << ' ' << cur_sum << ' ' << R << '\n';
    while (cur_sum > R) {
      const auto [w, k] = query_path(tin[i], tout[i]).min_w;
      ll v = worst(k);
      assert(k >= 0 && v >= L);
      ans += 1ll * w * min(cur_sum - R, v - L);
      update_path(k, -min(cur_sum - R, v - L));
      cur_sum -= min(cur_sum - R, v - L);
      v -= min(cur_sum - R, v - L);
      if (v == L)
        update_set(tin[k]);
    }
    update_mss(tin[i], cur_sum);
    return cur_sum;
  };
  dfs(dfs, 0);
  return ans;
}

void dfs_szs(const int i) {
  szs[i] = 1;
  hson[i] = -1;
  for (const auto &j : adj[i]) {
    dfs_szs(j);
    szs[i] += szs[j];
    if (hson[i] < 0 || szs[j] > szs[hson[i]])
      hson[i] = j;
  }
}
void dfs_hld(const int i) {
  rev_tin[tin[i] = timer++] = i;
  if (hson[i] >= 0) {
    head[hson[i]] = head[i];
    dfs_hld(hson[i]);
  }
  for (const auto &j : adj[i])
    if (j != hson[i]) {
      head[j] = j;
      dfs_hld(j);
    }
  tout[i] = timer - 1;
}

void init(vt<int> _P, vt<int> _W) {
  P = _P, W = _W, N = size(P);
  FOR(i, 1, N-1)
    adj[P[i]].push_back(i);
  dfs_szs(0);
  dfs_hld(0);
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 10
• Subtask 2: 13 / 13
• Subtask 3: 18 / 18
• Subtask 4: 0 / 7
• Subtask 5: 0 / 11
• Subtask 6: 0 / 22
• Subtask 7: 0 / 19