Submission #658636

#	Time	Username	Problem	Language	Result	Execution time	Memory
658636		lunchbox1	Dynamic Diameter (CEOI19_diameter)	C++17	100 / 100	463 ms	46988 KiB

diameter

/*
 Dynamic Diameter
 https://oj.uz/problem/view/CEOI19_diameter
*/
#include <bits/stdc++.h>
using namespace std;

const int N = 1e5, N_ = N * 2 - 1;

struct dat {
 long long a, b, ab, bc, abc;

 void lazy(long long x) {
  a += x;
  b -= 2 * x;
  ab -= x;
  bc -= x;
 }
 dat operator+(const dat& o) const {
  return {
   max(a, o.a),
   max(b, o.b),
   max(a + o.b, max(ab, o.ab)),
   max(b + o.a, max(bc, o.bc)),
   max(max(a + o.bc, ab + o.a), max(abc, o.abc))
  };
 }
} t[N_ * 4];

long long lz[N_ * 4];

vector<pair<int, long long>> g[N];
int d[N], in[N], out[N], tt;

void dfs(int p, int i) {
 in[i] = tt++;
 for (auto [j, c] : g[i])
  if (p != j)
   d[j] = d[i] + 1, dfs(i, j), tt++;
 out[i] = tt - 1;
}

void put(int k, long long x) {
 t[k].lazy(x);
 lz[k] += x;
}

void push(int k) {
 if (lz[k] != 0)
  put(k << 1 | 0, lz[k]), put(k << 1 | 1, lz[k]), lz[k] = 0;
}

void update(int k, int l, int r, int ql, int qr, long long x) {
 if (ql > r || qr < l)
  return;
 else if (ql <= l && qr >= r)
  put(k, x);
 else {
  int m = (l + r) / 2;
  push(k);
  update(k << 1 | 0, l, m, ql, qr, x), update(k << 1 | 1, m + 1, r, ql, qr, x);
  t[k] = t[k << 1 | 0] + t[k << 1 | 1];
 }
}

int main() {
 ios::sync_with_stdio(0), cin.tie(0);
 int n, q;
 long long A;
 cin >> n >> q >> A;
 static tuple<int, int, long long> e[N - 1];
 for (int h = 0; h < n - 1; h++) {
  int i, j;
  long long c;
  cin >> i >> j >> c, i--, j--;
  g[i].push_back({j, c}), g[j].push_back({i, c});
  e[h] = {i, j, c};
 }
 tt = 0;
 dfs(-1, 0);
 assert(tt <= N_);
 for (int h = 0; h < n - 1; h++) {
  auto &[i, j, c] = e[h];
  if (d[i] < d[j])
   swap(i, j);
  update(1, 0, tt - 1, in[i], out[i], c);
 }
 long long last = 0;
 while (q--) {
  int h;
  long long c;
  cin >> h >> c, h = (h + last) % (n - 1), c = (c + last) % A;
  auto &[i, j, c_] = e[h];
  update(1, 0, tt - 1, in[i], out[i], c - c_), c_ = c;
  cout << (last = t[1].abc) << '\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