Submission #1087774

#	Time	Username	Problem	Language	Result	Execution time	Memory
1087774		juicy	Dynamic Diameter (CEOI19_diameter)	C++17	100 / 100	197 ms	45908 KiB

diameter

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

using Node = array<long long, 5>; // (ans, prefix, suffix, min, max)

Node operator + (const Node &lt, const Node &rt) {
  Node res{};
  res[0] = max({lt[0], rt[0], lt[2] + rt[4], lt[4] + rt[1]});
  res[1] = max({lt[1], rt[1], rt[4] - 2 * lt[3]});
  res[2] = max({lt[2], rt[2], lt[4] - 2 * rt[3]});
  res[3] = min(lt[3], rt[3]);
  res[4] = max(lt[4], rt[4]);
  return res; 
}

const int N = 1e5 + 5;

int n, q;
int pos[2 * N], L[N], R[N], ver[N];
long long dep[N], lz[8 * N], w[N];
Node s[8 * N];
vector<array<int, 2>> g[N];

void app(int id, long long x) {
  lz[id] += x;
  s[id][1] -= x;
  s[id][2] -= x;
  s[id][3] += x;
  s[id][4] += x;
}

void psh(int id) {
  if (lz[id]) {
    app(id * 2, lz[id]);
    app(id * 2 + 1, lz[id]);
    lz[id] = 0;
  }
}

void bld(int id = 1, int l = 1, int r = 2 * n - 1) {
  if (l == r) {
    long long h = dep[pos[l]];
    s[id] = {0, -h, -h, h, h};
    return;
  }
  int m = (l + r) / 2;
  bld(id * 2, l, m);
  bld(id * 2 + 1, m + 1, r);
  s[id] = s[id * 2] + s[id * 2 + 1];
}

void upd(int u, int v, long long x, int id = 1, int l = 1, int r = 2 * n - 1) {
  if (u <= l && r <= v) {
    app(id, x);
    return;
  }
  psh(id);
  int m = (l + r) / 2;
  if (u <= m) {
    upd(u, v, x, id * 2, l, m);
  }
  if (m < v) {
    upd(u, v, x, id * 2 + 1, m + 1, r);
  }
  s[id] = s[id * 2] + s[id * 2 + 1];
}

int timer;

void dfs(int u) {
  pos[L[u] = ++timer] = u;
  for (auto [v, id] : g[u]) {
    if (!L[v]) {
      ver[id] = v;
      dep[v] = dep[u] + w[id];
      dfs(v);
      pos[++timer] = u;
    }
  }
  R[u] = timer;
}

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

  long long W; cin >> n >> q >> W;
  for (int i = 1; i < n; ++i) {
    int u, v; cin >> u >> v >> w[i];
    g[u].push_back({v, i});
    g[v].push_back({u, i});
  }
  dfs(1);
  bld();
  long long lst = 0;
  while (q--) {
    int id; long long e; cin >> id >> e;
    id = (id + lst) % (n - 1) + 1;
    e = (e + lst) % W;
    int u = ver[id];
    upd(L[u], R[u], e - w[id]);
    w[id] = e;
    cout << (lst = s[1][0]) << "\n";
  }
  return 0;
}

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