Submission #1278124

#	Time	Username	Problem	Language	Result	Execution time	Memory
1278124		LIA	Dynamic Diameter (CEOI19_diameter)	C++17	31 / 100	489 ms	28624 KiB

diameter

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define f first
#define s second
const ll inf = 1e18;
#define vll vector<ll>
ll n, q, w;
vector<tuple<ll, ll, ll>> edges;
vector<ll> tin, tout, par, comp, vin;
ll timer = 0;
vector<vector<ll>> g;
void dfs(ll node, ll pari) {
  par[node] = pari;
  tin[node] = timer++;
  vin[tin[node]] = node;
  for (auto it : g[node]) {
    if (it == pari)
      continue;
    dfs(it, node);
  }
  tout[node] = timer - 1;
}
void dfs2(ll node, ll pari, ll id) {
  comp[node] = id;
  for (auto it : g[node]) {
    if (it == pari)
      continue;
    dfs2(it, node, node == 0 ? it : id);
  }
}
struct cand {
  ll val;
  ll id;
};
struct node {
  cand a, b;
  ll lazy;
};
node merge(node A, node B) {
  vector<cand> v = {A.a, A.b, B.a, B.b};
  sort(v.begin(), v.end(), [](cand x, cand y) { return x.val > y.val; });
  node res;
  res.a = v[0];
  res.b = {-(ll)4e18, -1};
  for (auto x : v)
    if (x.id != res.a.id) {
      res.b = x;
      break;
    }
  res.lazy = 0;
  return res;
}
struct Seg {
  vector<node> seg;
  ll sz = 1;
  Seg() {
    tin.resize(n), tout.resize(n), par.resize(n), comp.resize(n), vin.resize(n);
    timer = 0;
    dfs(0, -1);
    dfs2(0, -1, -1);
    for (; sz < n; sz *= 2)
      ;
    seg.resize(2 * sz);
    for (ll i = 0; i < n; i++) {
      ll v = vin[i];
      seg[sz + i].a = {0, comp[v]};
      seg[sz + i].b = {-(ll)4e18, -1};
    }
    for (ll i = sz - 1; i >= 1; --i)
      seg[i] = merge(seg[i * 2], seg[i * 2 + 1]);
  }
  void push(ll i) {
    ll x = seg[i].lazy;
    if (x == 0)
      return;
    seg[i * 2].a.val += x;
    seg[i * 2].b.val += x;
    seg[i * 2].lazy += x;
    seg[i * 2 + 1].a.val += x;
    seg[i * 2 + 1].b.val += x;
    seg[i * 2 + 1].lazy += x;
    seg[i].lazy = 0;
  }
  void update(ll i, ll l, ll r, ll a, ll b, ll w) {
    if (l > b || r < a)
      return;
    if (l >= a && r <= b) {
      seg[i].a.val += w;
      seg[i].b.val += w;
      seg[i].lazy += w;
      return;
    }
    push(i);
    ll mid = (l + r) / 2;
    update(i * 2, l, mid, a, b, w);
    update(i * 2 + 1, mid + 1, r, a, b, w);
    seg[i] = merge(seg[i * 2], seg[i * 2 + 1]);
  }
  void update(ll node, ll w) {
    ll l = tin[node], r = tout[node];
    update(1, 0, sz - 1, l, r, w);
  }
  ll ans() {
    return seg[1].a.val + seg[1].b.val;
  }
};
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cin >> n >> q >> w;
  edges.resize(n - 1);
  g.resize(n);
  for (ll i = 0; i < n - 1; ++i) {
    ll a, b, c;
    cin >> a >> b >> c;
    a--;
    b--;
    edges[i] = {a, b, c};
    g[a].push_back(b);
    g[b].push_back(a);
  }
  Seg seg;
  par[0] = -1;
  for (ll i = 0; i < n - 1; ++i) {
    auto& [a, b, c] = edges[i];
    if (par[b] != a)
      swap(a, b);
    seg.update(b, c);
  }
  ll last = 0;
  while (q--) {
    ll d, e;
    cin >> d >> e;
    ll d1 = (d + last) % (n - 1);
    ll e1 = (e + last) % w;
    auto& [a, b, c] = edges[d1];
    ll dis = e1 - c;
    seg.update(b, dis);
    c = e1;
    last = seg.ans();
    cout << last << "\n";
  }
}

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