Submission #424419

#	Time	Username	Problem	Language	Result	Execution time	Memory
424419		Hegdahl	Dynamic Diameter (CEOI19_diameter)	C++17	100 / 100	547 ms	48544 KiB

diameter

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define ar array

using namespace std;
using ll = long long;

const int mxN = 1e5;
vector<ar<ll, 2>> g[mxN];
int frst[mxN], last[mxN];
ll depth[mxN];

vector<int> order;
void dfs(int cur, int prv, ll d) {
  frst[cur] = (int)order.size();
  last[cur] = (int)order.size();
  depth[cur] = d;
  order.push_back(cur);

  for (auto [nxt, w] : g[cur]) {
    if (nxt == prv) continue;
    dfs((int)nxt, cur, d+w);
    last[cur] = (int)order.size();
    order.push_back(cur);
  }
}

const ll INF = 1LL<<60;

struct S {
  ll lmin, lmax, mmin, rmax, rmin, longest;

  S() : lmin(INF), lmax(INF), mmin(INF), rmax(INF), rmin(INF), longest(INF) {}
  S(ll d) : lmin(d), lmax(d), mmin(d), rmax(d), rmin(d), longest(0) {}
  S(ll lm, ll l, ll m, ll r, ll rm) :
    lmin(lm), lmax(l), mmin(m), rmax(r), rmin(rm), longest(l + r - 2*m) {}

  bool operator<(const S &o) const {
    return longest < o.longest;
  }

  void pull(S l, S r) {
    if (l.lmin == INF) return void(*this = r);
    if (r.lmin == INF) return void(*this = l);

    ar mx {l.lmax, l.rmax, r.lmax, r.rmax};
    ar mn {l.lmin, l.mmin, min(l.rmin, r.lmin), r.mmin, r.rmin};
    ar premin = mn, sufmin = mn;
    for (int i = 1; i < 5; ++i) premin[i] = min(premin[i], premin[i-1]);
    for (int i = 3; i >= 0; --i) sufmin[i] = min(sufmin[i], sufmin[i+1]);

    ar alts {
      S(premin[0], mx[0], min({mn[1]}), mx[1], sufmin[2]),
      S(premin[0], mx[0], min({mn[1], mn[2]}), mx[2], sufmin[3]),
      S(premin[0], mx[0], min({mn[1], mn[2], mn[3]}), mx[3], sufmin[4]),
      S(premin[1], mx[1], min({mn[2]}), mx[2], sufmin[3]),
      S(premin[1], mx[1], min({mn[2], mn[3]}), mx[3], sufmin[4]),
      S(premin[2], mx[2], min({mn[3]}), mx[3], sufmin[4]),
    };

    *this = *max_element(alts.begin(), alts.end());
  }
};

struct F {
  ll s = 0;
  void apply(F &f) {
    f.s += s;
  }
  void apply(S &v) {
    v.lmin += s;
    v.lmax += s;
    v.mmin += s;
    v.rmax += s;
    v.rmin += s;
  }
};

const int mxL = mxN + mxN-1;
const int offset = 2<<__lg(mxL-1);
S values[2*offset];
F lazy[offset];

int push(int I, int l, int r) {
  lazy[I].apply(values[2*I]);
  lazy[I].apply(values[2*I+1]);
  if (2*I < offset) {
    lazy[I].apply(lazy[2*I]);
    lazy[I].apply(lazy[2*I+1]);
  }
  lazy[I] = F();

  return l + (r-l+1)/2;
}

S qry(int i, int j, int I = 1, int l = 0, int r = offset-1) {
  assert(!(i > r || j < l));
  if (i <= l && j >= r) return values[I];

  int mid = push(I, l, r);
  S res;
  res.pull(
    (i<mid?qry(i, j, 2*I, l, mid-1):S()),
    (j>=mid?qry(i, j, 2*I+1, mid, r):S())
  );
  return res;
}

void upd(int i, int j, F f, int I = 1, int l = 0, int r = offset-1) {
  assert(!(i > r || j < l));
  if (i <= l && j >= r) {
    f.apply(values[I]);
    if (I < offset) f.apply(lazy[I]);
    return;
  }

  int mid = push(I, l, r);
  if (i < mid) upd(i, j, f, 2*I, l, mid-1);
  if (j >= mid) upd(i, j, f, 2*I+1, mid, r);
  values[I].pull(values[2*I], values[2*I+1]);
}

int main() {
  cin.tie(0)->sync_with_stdio(0);

  int n, q; ll mxw; cin >> n >> q >> mxw;
  vector<ar<ll, 3>> e(n-1);
  for (auto &[i, j, w] : e) {
    cin >> i >> j >> w; --i, --j;
    g[i].push_back({j, w});
    g[j].push_back({i, w});
  }

  dfs(0, -1, 0);
  assert((int)order.size() == 2*n-1);
  assert(offset >= order.size());

  for (int i = 0; i < (int)order.size(); ++i)
    values[offset+i] = S(depth[order[i]]);

  for (int i = offset-1; i > 0; --i)
    values[i].pull(values[2*i], values[2*i+1]);

  ll ans = 0;
  for (int qq = 0; qq < q; ++qq) {
    int ei; ll w; cin >> ei >> w;
    ei = int((ei+ans)%(n-1));
    w = (w+ans)%mxw;
    auto &[i, j, pw] = e[ei];
    if (depth[i] > depth[j]) swap(i, j);

    ll change = w-pw;
    pw = w;

    upd(frst[j], last[j], {change});
    ans = qry(0, offset-1).longest;

    cout << ans << '\n';
  }
}

• Subtask 1: 11 / 11
• Subtask 2: 13 / 13
• Subtask 3: 7 / 7
• Subtask 4: 18 / 18
• Subtask 5: 24 / 24
• Subtask 6: 27 / 27