Submission #856625

#	Time	Username	Problem	Language	Result	Execution time	Memory
856625		hocky	Dynamic Diameter (CEOI19_diameter)	C++14	100 / 100	395 ms	98308 KiB

diameter

#include "bits/stdc++.h"

using namespace std;
const int LIM = 100000;
#define fi first
#define se second
typedef long long LL;
typedef pair<LL, LL> PLL;

namespace DynamicDiameter {
vector <PLL> edge[LIM + 5];
int event[2 * LIM + 5];
int dfsTime = 0;
LL weights[LIM + 5], depth[LIM + 5];
PLL order[LIM + 5];
void eulerTour(int pos, int par = -1) {
  dfsTime++;
  order[pos].fi = dfsTime;
  event[dfsTime] = pos;
  for (auto &nx : edge[pos]) {
    if (nx.fi == par) continue;
    depth[nx.fi] = depth[pos] + nx.se;
    weights[nx.fi] = nx.se;
    eulerTour(nx.fi, pos);
    dfsTime++;
    event[dfsTime] = pos;
  }
  order[pos].se = dfsTime;
  return;
}

const LL INF = 1e14;
// Segment Tree starts here
struct Node {
  PLL maxDepth = {-INF, -1}, minDepth = {INF, -1};
  PLL leftMax = {-INF, -1}, rightMax = {-INF, -1};
  pair<LL, PLL> diameter = {-1, {-1, -1}};
  LL lazy;
};

Node segt[8 * LIM + 5];
void pushDown(int rangeL = 1, int rangeR = dfsTime, int idx = 1) {
  if (segt[idx].lazy == 0) return;
  auto &val = segt[idx].lazy;
  segt[idx].maxDepth.fi += val;
  segt[idx].minDepth.fi += val;
  segt[idx].leftMax.fi -= val;
  segt[idx].rightMax.fi -= val;
  if (rangeL != rangeR) {
    segt[idx * 2].lazy += val;
    segt[idx * 2 + 1].lazy += val;
  }
  val = 0;
  return;
}
void merge(Node &head, Node &l, Node &r) {
  head.maxDepth = max(l.maxDepth, r.maxDepth);
  head.minDepth = min(l.minDepth, r.minDepth);

  head.leftMax = max(l.leftMax, r.leftMax);
  head.leftMax = max(head.leftMax, {l.maxDepth.fi - 2 * r.minDepth.fi, l.maxDepth.se});

  head.rightMax = max(l.rightMax, r.rightMax);
  head.rightMax = max(head.rightMax, {r.maxDepth.fi - 2 * l.minDepth.fi, r.maxDepth.se});

  head.diameter = max(l.diameter, r.diameter);
  head.diameter = max(head.diameter, {l.maxDepth.fi + r.rightMax.fi, {l.maxDepth.se, r.rightMax.se}});
  head.diameter = max(head.diameter, {r.maxDepth.fi + l.leftMax.fi, {r.maxDepth.se, l.leftMax.se}});
  //~ cout << head.maxDepth << " " << head.minDepth << " " << head.leftMax << " " << head.rightMax << " " << head.diameter << endl;
}
void build(int rangeL = 1, int rangeR = dfsTime, int idx = 1) {
  //~ cout << rangeL << " " << rangeR << " " << idx << endl;
  if (rangeL == rangeR) {
    segt[idx].minDepth = segt[idx].maxDepth = {depth[event[rangeL]], event[rangeL]};
    segt[idx].leftMax = segt[idx].rightMax = {-depth[event[rangeL]], event[rangeL]};
    return;
  }
  int mid = (rangeL + rangeR) >> 1;
  build(rangeL, mid, idx * 2);
  build(mid + 1, rangeR, idx * 2 + 1);
  merge(segt[idx], segt[idx * 2], segt[idx * 2 + 1]);
}
void update(int queryL, int queryR, LL val, int rangeL = 1, int rangeR = dfsTime, int idx = 1) {
  pushDown(rangeL, rangeR, idx);
  if (rangeR < queryL) return;
  if (queryR < rangeL) return;
  if (queryL <= rangeL && rangeR <= queryR) {
    segt[idx].lazy = val;
    pushDown(rangeL, rangeR, idx);
    return;
  }
  int mid = (rangeL + rangeR) >> 1;
  update(queryL, queryR, val, rangeL, mid, idx * 2);
  update(queryL, queryR, val, mid + 1, rangeR, idx * 2 + 1);
  merge(segt[idx], segt[idx * 2], segt[idx * 2 + 1]);
  return;
}
}

using namespace DynamicDiameter;

int main() {
  cin.tie(0) -> sync_with_stdio(0);
  cout.tie(0);
  LL n, q, w; cin >> n >> q >> w;
  vector <PLL> edges(n - 1);
  for (int i = 0; i < n - 1; i++) {
    LL c;
    cin >> edges[i].fi >> edges[i].se >> c;
    edge[edges[i].fi].emplace_back(edges[i].se, c);
    edge[edges[i].se].emplace_back(edges[i].fi, c);
  }
  eulerTour(1);
  //~ for(int i = 1;i <= dfsTime;i++) cout << event[i] << " ";
  //~ cout << endl;
  //~ for(int i = 1;i <= n;i++) cout << i << " " << order[i].fi << " " << order[i].se << endl;
  build();
  LL ans = 0;
  //~ cout << segt[1].diameter << endl;
  //~ return 0;
  while (q--) {
    LL d, e; cin >> d >> e;
    d = (d + ans) % (n - 1);
    e = (e + ans) % w;
    auto &edge = edges[d];
    if (order[edge.fi].fi > order[edge.se].fi) {
      swap(edge.fi, edge.se);
    }
    // Update the segment tree
    //~ cout << e - weights[edge.se] << endl;
    //~ cout << segt[1].diameter << endl;
    update(order[edge.se].fi, order[edge.se].se, e - weights[edge.se]);
    weights[edge.se] = e;
    ans = segt[1].diameter.fi;
    // auto curPair = segt[1].diameter.se;
    // cout << curPair.fi << " " << curPair.se << endl;
    cout << ans << endl;
  }
}

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