Submission #885164

#	Time	Username	Problem	Language	Result	Execution time	Memory
885164		nima_aryan	Dynamic Diameter (CEOI19_diameter)	C++17	100 / 100	417 ms	46596 KiB

diameter

/**
 *    author:  NimaAryan
 *    created: 2023-12-09 09:11:54  
**/
#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "algo/debug.h"
#endif

using i64 = long long;

struct Tag {
  i64 add = 0;

  void apply(Tag v) {
    add += v.add;
  }
};
struct Info {
  i64 min_dep = 0;
  i64 max_dep = 0;
 
  /* max(dep[x] - 2 * dep[y]) */
  i64 limp = 0;
  i64 rimp = 0;

  i64 diam = 0;

  void apply(Tag v) {
    min_dep += v.add;
    max_dep += v.add;
    limp -= v.add;
    rimp -= v.add;
  }
};
Info operator+(Info a, Info b) {
  Info res;
  res.min_dep = min(a.min_dep, b.min_dep);
  res.max_dep = max(a.max_dep, b.max_dep);
  res.limp = max({a.limp, b.limp, a.max_dep - 2LL * b.min_dep});
  res.rimp = max({a.rimp, b.rimp, b.max_dep - 2LL * a.min_dep});
  res.diam = max({a.diam, b.diam, a.max_dep + b.rimp, b.max_dep + a.limp});
  return res;
}

class LazySegmentTree {
 public:
  vector<Info> info;
  vector<Tag> tag;
  int n;

  LazySegmentTree(int n) : n(n) {
    info.assign(4 << __lg(n), Info());
    tag.assign(4 << __lg(n), Tag());
  }

  void pull(int p) {
    info[p] = info[2 * p] + info[2 * p + 1];
  }
  void apply(int p, const Tag& v) {
    info[p].apply(v);
    tag[p].apply(v);
  }
  void push(int p) {
    apply(2 * p, tag[p]);
    apply(2 * p + 1, tag[p]);
    tag[p] = Tag();
  }
  void range_apply(int p, int l, int r, int lx, int rx,
                  const Tag& v) {
    if (l >= rx || r <= lx) {
      return;
    }
    if (l >= lx && r <= rx) {
      apply(p, v);
      return;
    }
    int m = (l + r) / 2;
    push(p);
    range_apply(2 * p, l, m, lx, rx, v);
    range_apply(2 * p + 1, m, r, lx, rx, v);
    pull(p);
  }
  void range_apply(int lx, int rx, const Tag& v) {
    range_apply(1, 0, n, lx, rx, v);
  }
};

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

  vector<vector<pair<int, i64>>> t(n);
  vector<i64> c(n - 1);
  for (int i = 0; i < n - 1; ++i) {
    int a, b;
    cin >> a >> b;
    --a, --b;
    cin >> c[i];
    t[a].emplace_back(b, i);
    t[b].emplace_back(a, i);
  }

  LazySegmentTree seg(2 * n - 1);
  vector<int> tin(n - 1), tout(n - 1);
  int num = 0;
  auto dfs = [&](auto self, int x, int p) -> void {
    num++;
    for (auto [y, i] : t[x]) {
      if (i != p) {
        tin[i] = num;
        self(self, y, i);
        tout[i] = num;
        seg.range_apply(tin[i], tout[i], Tag{c[i]});
        num++;
      }
    }
  };
  dfs(dfs, 0, -1);

  i64 last = 0;
  while (q--) {
    int d;
    cin >> d;
    i64 e;
    cin >> e;
    d = (d + last) % (n - 1);
    e = (e + last) % w;
    seg.range_apply(tin[d], tout[d], Tag{-c[d]});
    c[d] = e;
    seg.range_apply(tin[d], tout[d], Tag{+c[d]});
    cout << (last = seg.info[1].diam) << "\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