oj.uz

답안 #402016

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
402016 2021-05-11T07:45:31 Z rama_pang Arboras (RMI20_arboras) C++17
100 / 100
 1633 ms 26316 KB 
#include <bits/stdc++.h>
using namespace std;

using lint = long long;
const lint INF = 1e18;
const lint MOD = 1e9 + 7;

class SegTree {
 public:
  int sz;
  vector<int> cnt;
  vector<lint> tree;
  vector<lint> lazy;

  SegTree(int sz) : sz(sz), cnt(2 * sz), tree(2 * sz), lazy(2 * sz) {
    Build(1, 0, sz - 1);
  }

  void Build(int n, int tl, int tr) {
    if (tl == tr) {
      cnt[n] = 1;
      tree[n] = 0;
      lazy[n] = 0;
      return;
    }
    int md = (tl + tr) / 2;
    int z = n + 2 * (md - tl + 1);
    Build(n + 1, tl, md);
    Build(z, md + 1, tr);
    Pull(n, n + 1, z);
  }

  void Pull(int n, int lc, int rc) {
    cnt[n] = cnt[lc] + cnt[rc];
    tree[n] = tree[lc] + tree[rc];
    if (cnt[n] > 1) {
      tree[n] %= MOD;
    }
  }

  void Apply(int n, lint x) {
    tree[n] += cnt[n] * x;
    lazy[n] += x;
    if (cnt[n] > 1) {
      tree[n] %= MOD;
    }
  }

  void Push(int n, int lc, int rc) {
    Apply(lc, lazy[n]);
    Apply(rc, lazy[n]);
    lazy[n] = 0;
  }

  void Update(int n, int tl, int tr, int l, int r, lint x) {
    if (l > tr || tl > r || tl > tr || l > r) return;
    if (l <= tl && tr <= r) return Apply(n, x);
    int md = (tl + tr) / 2;
    int z = n + 2 * (md - tl + 1);
    Push(n, n + 1, z);
    Update(n + 1, tl, md, l, r, x);
    Update(z, md + 1, tr, l, r, x);
    Pull(n, n + 1, z);
  }

  void Update(int l, int r, lint x) {
    Update(1, 0, sz - 1, l, r, x);
  }

  lint Query(int p) {
    int n = 1, tl = 0, tr = sz - 1;
    while (tl != tr) {
      int md = (tl + tr) / 2;
      int z = n + 2 * (md - tl + 1);
      Push(n, n + 1, z);
      if (p <= md) {
        n = n + 1;
        tr = md;
      } else {
        n = z;
        tl = md + 1;
      }
    }
    assert(tl == tr);
    return tree[n];
  }

  lint Query() {
    return tree[1];
  }
};

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);

  int N;
  cin >> N;

  vector<int> st(N);
  vector<int> ist(N);
  vector<int> siz(N);
  vector<int> par(N);
  vector<int> root(N);
  vector<int> depth(N);
  vector<vector<int>> adj(N);

  par[0] = -1;
  for (int i = 1; i < N; i++) {
    cin >> par[i];
    adj[par[i]].emplace_back(i);
  }

  const auto DfsInit = [&](const auto &self, int u) -> void {
    siz[u] = 1;
    for (auto &v : adj[u]) {
      depth[v] = depth[u] + 1;
      self(self, v);
      siz[u] += siz[v];
      if (siz[v] > siz[adj[u][0]]) {
        swap(v, adj[u][0]);
      }
    }
  };

  const auto DfsHld = [&](const auto &self, int u) -> void {
    static int timer = 0;
    st[u] = timer++;
    ist[st[u]] = u;
    for (auto v : adj[u]) {
      root[v] = v == adj[u][0] ? root[u] : v;
      self(self, v);
    }
  };

  DfsInit(DfsInit, 0);
  DfsHld(DfsHld, 0);

  // Complexity by Link-Cut Tree Heavy-Light analysis
  // Keep segment tree, with dp[v] on position v
  // Update link-cut style on HLD
  // Time: O((N + Q) log^2 N).

  set<int> chain;
  for (int i = 0; i < N; i++) {
    chain.emplace(st[i]);
  }

  const auto ModifyChain = [&](int u, int sgn) {
    if (sgn == -1) {
      chain.erase(chain.find(st[u]));
    } else if (sgn == +1) {
      chain.emplace(st[u]);
    }
  };

  SegTree dp_1(N);
  SegTree dp_2(N);
  vector<int> prefer(N, -1);
  vector<lint> weight(N);

  const auto Update = [&](const auto &self, int prv) -> void {
    if (prv == 0) return;
    int u = par[prv];
    lint newdp = dp_1.Query(st[prv]) + weight[prv];

    if (newdp <= dp_2.Query(st[u])) {
      // do nothing
    } else if (dp_2.Query(st[u]) < newdp && newdp <= dp_1.Query(st[u])) {
      dp_2.Update(st[u], st[u], newdp - dp_2.Query(st[u]));
    } else if (dp_1.Query(st[u]) < newdp) {
      lint dp1 = dp_1.Query(st[u]);
      lint dp2 = dp_2.Query(st[u]);
      int head = ist[*prev(chain.upper_bound(st[u]))];
      assert(root[u] == root[head]);

      if (prefer[u] == prv) {
        dp_1.Update(st[head], st[u], newdp - dp1);
        return self(self, head);
      }

      if (prefer[u] != -1) {
        // insert prefer[u] as head chain
        ModifyChain(prefer[u], +1);
        prefer[u] = -1;
      }
      prefer[u] = prv;
      if (root[u] == root[prv]) {
        // delete prv as head chain
        ModifyChain(prv, -1);
      }

      dp_2.Update(st[u], st[u], dp1 - dp2);
      dp_1.Update(st[head], st[u], newdp - dp1);

      return self(self, head);
    }
  };

  const auto Print = [&]() {
    for (int i = 0; i < N; i++) {
      cout << i << ' ' << dp_1.Query(st[i]) << ' ' << dp_2.Query(st[i]) << '\n';
    }
    cout << '\n';
  };

  for (int i = 1; i < N; i++) {
    int w;
    cin >> w;
    weight[i] += w;
    Update(Update, i);
  }

  cout << (dp_1.Query() + dp_2.Query()) % MOD << '\n';

  int Q;
  cin >> Q;
  while (Q--) {
    int u, w;
    cin >> u >> w;
    weight[u] += w;
    Update(Update, u);
    cout << (dp_1.Query() + dp_2.Query()) % MOD << '\n';
    // Print();
  }
  return 0;
}

Compilation message

arboras.cpp: In function 'int main()':
arboras.cpp:200:14: warning: variable 'Print' set but not used [-Wunused-but-set-variable]
  200 |   const auto Print = [&]() {
      |              ^~~~~

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 460 KB Output is correct
2 Correct 3 ms 460 KB Output is correct
3 Correct 3 ms 460 KB Output is correct

Subtask #2
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1633 ms 23408 KB Output is correct
2 Correct 311 ms 21720 KB Output is correct
3 Correct 344 ms 21956 KB Output is correct

Subtask #3
31.0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1290 ms 24700 KB Output is correct
2 Correct 623 ms 25640 KB Output is correct
3 Correct 436 ms 22880 KB Output is correct

Subtask #4
45.0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 460 KB Output is correct
2 Correct 3 ms 460 KB Output is correct
3 Correct 3 ms 460 KB Output is correct
4 Correct 1633 ms 23408 KB Output is correct
5 Correct 311 ms 21720 KB Output is correct
6 Correct 344 ms 21956 KB Output is correct
7 Correct 1290 ms 24700 KB Output is correct
8 Correct 623 ms 25640 KB Output is correct
9 Correct 436 ms 22880 KB Output is correct
10 Correct 1384 ms 24492 KB Output is correct
11 Correct 617 ms 25360 KB Output is correct
12 Correct 548 ms 22896 KB Output is correct
13 Correct 1059 ms 25824 KB Output is correct
14 Correct 1004 ms 26316 KB Output is correct