Submission #1277887

#	Time	Username	Problem	Language	Result	Execution time	Memory
1277887		LIA	Dynamic Diameter (CEOI19_diameter)	C++17	0 / 100	114 ms	16732 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;
ll timer = 0;
vector<vector<ll>> g;

void dfs(ll node, ll pari) {
  tin[node] = timer++;
  for (auto it : g[node]) {
    if (it == pari)
      continue;
    par[it] = node;
    dfs(it, node);
  }
  tout[node] = timer - 1;
}

struct Seg {
  vll seg, lazy_add;
  ll sz = 1;
  Seg() {
    tin.resize(n), tout.resize(n), par.resize(n);
    dfs(0, -1);
    for (; sz < n; sz *= 2)
      ;
    seg.resize(2 * sz), lazy_add.resize(2 * sz);
  }

  void update(ll node, ll w) {
    ll l = tin[node], r = tout[node];
    update(1, 0, n - 1, l, r, w);
  }

  void push(ll i, ll l, ll r) {
    ll& x = lazy_add[i];
    if (x) {
      seg[i] += x;
      if (l != r) {
        lazy_add[i * 2] += x;
        lazy_add[i * 2 + 1] += x;
      }
    }
    x = 0;
  }

  void update(ll i, ll l, ll r, ll a, ll b, ll w) {

    if (l > b || r < a)
      return;
    push(i, l, r);
    if (l >= a && r <= b) {
      lazy_add[i] += w;
      push(i, l, r);
      return;
    }
    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] = max(seg[i * 2], seg[i * 2 + 1]);
  }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cin >> n >> q >> w;

  edges.resize(n);
  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];
    // a=par[b]
    if (par[a] == b)
      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.seg[1];

    cout << last << " ";
  }
  // cout<<"Cds";
  return 0;
}

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