Submission #1255070

#	Time	Username	Problem	Language	Result	Execution time	Memory
1255070		daotuankhoi	Dynamic Diameter (CEOI19_diameter)	C++20	100 / 100	245 ms	53772 KiB

diameter

#include <bits/stdc++.h>

using namespace std;

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

template <class T> bool ckmax(T &a, T b) { return a < b ? (a = b, true) : false; }
template <class T> bool ckmin(T &a, T b) { return a > b ? (a = b, true) : false; }

#define int long long

/*
  Dung euler tour 2n-1. Khi do duong kinh la max cua bieu thuc:
  dep[i] - 2 * dep[j] + dep[k]
  i < j < k
  Luc nay j la lca cua (i, k)
*/

const int MAXN = 4e5 + 5;
vector<pair<int, int>> g[MAXN];
tuple<int, int, int> e[MAXN];

int euler[MAXN], in[MAXN], out[MAXN], timeDfs = 0;
int dep[MAXN];

void dfs(int u, int p) {
  euler[++timeDfs] = u;
  in[u] = timeDfs;
  for (auto [v, w] : g[u]) {
    if (v != p) {
      dep[v] = dep[u] + w;
      dfs(v, u);
      euler[++timeDfs] = u;
    }
  }
  out[u] = timeDfs;
}

struct Node {
  int mndep, mxdep, mxsubL, mxsubR, diam;
  // mxsubL: dep[i] - 2 * dep[j]
  // mxsubR: -2 * dep[j] + dep[k]
  Node() {}
  Node(int val) {
    mndep = mxdep = val;
    mxsubL = mxsubR = -val;
    diam = 0;
  }
  Node operator+(const Node &other) const {
    Node res;
    res.mxdep = max(mxdep, other.mxdep);
    res.mndep = min(mndep, other.mndep);
    res.mxsubL = max({mxsubL, other.mxsubL, mxdep - 2 * other.mndep});
    res.mxsubR = max({mxsubR, other.mxsubR, -2 * mndep + other.mxdep});
    res.diam = max({diam, other.diam, mxsubL + other.mxdep, mxdep + other.mxsubR});
    return res;
  }
  void add(int val) {
    mxdep += val;
    mndep += val;
    mxsubL -= val;
    mxsubR -= val;
  }
};

struct segtree {
  Node st[MAXN * 4];
  int lazy[MAXN * 4];
  int n;

  void apply(int id, int val) {
    st[id].add(val);
    lazy[id] += val;
  }

  void push(int id) {
    if (lazy[id] == 0) return;
    apply(id << 1, lazy[id]);
    apply(id << 1 | 1, lazy[id]);
    lazy[id] = 0;
  }

  void build(int id, int l, int r) {
    lazy[id] = 0;
    if (l == r) {
      st[id] = Node(dep[euler[l]]);
      return;
    }
    int mid = (l + r) >> 1;
    build(id << 1, l, mid);
    build(id << 1 | 1, mid + 1, r);
    st[id] = st[id << 1] + st[id << 1 | 1];
  }

  void update(int id, int l, int r, int u, int v, int val) {
    if (v < l || r < u) return;
    if (u <= l && r <= v) {
      apply(id, val);
      return;
    }
    push(id);
    int mid = (l + r) >> 1;
    update(id << 1, l, mid, u, v, val);
    update(id << 1 | 1, mid + 1, r, u, v, val);
    st[id] = st[id << 1] + st[id << 1 | 1];
  }

  Node query(int id, int l, int r, int u, int v) {
    if (u <= l && r <= v) return st[id];
    push(id);
    int mid = (l + r) >> 1;
    if (u > mid) return query(id << 1 | 1, mid + 1, r, u, v);
    if (v <= mid) return query(id << 1, l, mid, u, v);
    return query(id << 1, l, mid, u, v) + query(id << 1 | 1, mid + 1, r, u, v);
  }

  void build(int N) {
    n = N;
    build(1, 1, n);
  }

  void update(int l, int r, int val) {
    update(1, 1, n, l, r, val);
  }

  Node get(int l, int r) {
    if (l > r) return Node();
    return query(1, 1, n, l, r);
  }
} st;

signed main() {
  #define NAME "test"
  if (fopen(NAME".inp", "r")) {
    freopen(NAME".inp", "r", stdin);
    freopen(NAME".out", "w", stdout);
  }
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int n, q;
  int maxWeight;
  cin >> n >> q >> maxWeight;
  for (int i = 1; i < n; i++) {
    int u, v, w; cin >> u >> v >> w;
    g[u].emplace_back(v, w);
    g[v].emplace_back(u, w);
    e[i] = {u, v, w};
  }
  dfs(1, 1);
  st.build(2 * n - 1);
  int last = 0;
  while (q--) {
    int d, ej; cin >> d >> ej;
    d = (d + last) % (n - 1) + 1;
    ej = (ej + last) % maxWeight;
    auto &[u, v, w] = e[d];
    if (dep[u] < dep[v]) swap(u, v);
    st.update(in[u], out[u], ej - w);
    w = ej;
    last = st.st[1].diam;
    cout << last << '\n';
  }
  return 0;
}

Compilation message (stderr)

diameter.cpp: In function 'int main()':
diameter.cpp:139:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  139 |     freopen(NAME".inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
diameter.cpp:140:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  140 |     freopen(NAME".out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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