제출 #1279640

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1279640		LIA	Dynamic Diameter (CEOI19_diameter)	C++17	11 / 100	5096 ms	1114112 KiB

diameter

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define f first
#define s second
const ll inf = 1e18;
#define vll vector<ll>
ll n, q, w;
vector<tuple<ll, ll, ll>> edges;
vector<ll> tin, tout, par, comp, vin;
ll timer = 0;
vector<vector<ll>> g;

void dfs(ll node, ll pari) {
  par[node] = pari;
  tin[node] = timer++;
  vin[tin[node]] = node;
  for (auto it : g[node]) {
    if (it == pari)
      continue;
    dfs(it, node);
  }
  tout[node] = timer - 1;
}

void dfs2(ll node, ll pari, ll id) {
  comp[node] = id;
  for (auto it : g[node]) {
    if (it == pari)
      continue;
    dfs2(it, node, node == 0 ? it : id);
  }
}

struct cand {
  ll val;
  ll id;
};

struct node {
  cand a, b;
  ll lazy;
};

node merge(node A, node B) {
  vector<cand> v = {A.a, A.b, B.a, B.b};
  sort(v.begin(), v.end(), [](cand x, cand y) { return x.val > y.val; });
  node res;
  res.a = v[0];
  res.b = {-(ll)4e18, -1};
  for (auto x : v)
    if (x.id != res.a.id) {
      res.b = x;
      break;
    }
  res.lazy = 0;
  return res;
}

struct Seg {
  vector<node> seg;
  ll sz = 1;
  Seg() {
    tin.resize(n), tout.resize(n), par.resize(n), comp.resize(n), vin.resize(n);
    timer = 0;
    dfs(0, -1);
    dfs2(0, -1, -1);
    for (; sz < n; sz *= 2)
      ;
    seg.resize(2 * sz);
    for (ll i = 0; i < n; i++) {
      ll v = vin[i];
      seg[sz + i].a = {0, comp[v]};
      seg[sz + i].b = {-(ll)4e18, -1};
    }
    for (ll i = sz - 1; i >= 1; --i)
      seg[i] = merge(seg[i * 2], seg[i * 2 + 1]);
  }
  void push(ll i) {
    ll x = seg[i].lazy;
    if (x == 0)
      return;
    seg[i * 2].a.val += x;
    seg[i * 2].b.val += x;
    seg[i * 2].lazy += x;
    seg[i * 2 + 1].a.val += x;
    seg[i * 2 + 1].b.val += x;
    seg[i * 2 + 1].lazy += x;
    seg[i].lazy = 0;
  }
  void update(ll i, ll l, ll r, ll a, ll b, ll w) {
    if (l > b || r < a)
      return;
    if (l >= a && r <= b) {
      seg[i].a.val += w;
      seg[i].b.val += w;
      seg[i].lazy += w;
      return;
    }
    push(i);
    ll mid = (l + r) / 2;
    update(i * 2, l, mid, a, b, w);
    update(i * 2 + 1, mid + 1, r, a, b, w);
    seg[i] = merge(seg[i * 2], seg[i * 2 + 1]);
  }
  void update(ll node, ll w) {
    ll l = tin[node], r = tout[node];
    update(1, 0, sz - 1, l, r, w);
  }
  ll ans() {
    return seg[1].a.val + seg[1].b.val;
  }
};

vector<vector<pair<ll, ll>>> wg;
vector<vector<pair<ll, ll>>> adj_e;
vector<ll> deadc, szt;
ll Nsz;
void getsz(ll u, ll p) {
  szt[u] = 1;
  for (auto [v, id] : adj_e[u]) {
    if (v == p || deadc[v])
      continue;
    getsz(v, u);
    szt[u] += szt[v];
  }
}
ll getcent(ll u, ll p, ll tot) {
  for (auto [v, id] : adj_e[u]) {
    if (v == p || deadc[v])
      continue;
    if (szt[v] * 2 > tot)
      return getcent(v, u, tot);
  }
  return u;
}
void collect_nodes(ll u, ll p, vector<ll>& vec) {
  vec.push_back(u);
  for (auto [v, id] : adj_e[u]) {
    if (v == p || deadc[v])
      continue;
    collect_nodes(v, u, vec);
  }
}

struct SegC {
  vector<node> seg;
  ll sz = 1;
  vector<ll> alive;
  vector<ll> compc;
  ll c;
  SegC(ll cc, const vector<ll>& nodes) {
    c = cc;
    for (; sz < n; sz *= 2)
      ;
    seg.resize(2 * sz);
    alive.assign(n, 0);
    compc.assign(n, -1);
    for (auto v : nodes)
      alive[v] = 1;
    vector<ll> dist(n, 0);
    deque<ll> dq;
    dq.push_back(c);
    vector<ll> vis(n, 0);
    vis[c] = 1;
    while (!dq.empty()) {
      ll u = dq.front();
      dq.pop_front();
      for (auto [v, id] : wg[u]) {
        if (vis[v] || deadc[v])
          continue;
        vis[v] = 1;
        dist[v] = dist[u] + get<2>(edges[id]);
        dq.push_back(v);
      }
    }
    function<void(ll, ll, ll)> dfscomp = [&](ll u, ll p, ll id) {
      compc[u] = id;
      for (auto [v, eid] : adj_e[u]) {
        if (v == p || deadc[v])
          continue;
        dfscomp(v, u, u == c ? v : id);
      }
    };
    dfscomp(c, -1, -1);
    for (ll i = 0; i < n; ++i) {
      ll v = vin[i];
      if (alive[v]) {
        seg[sz + i].a = {dist[v], compc[v]};
      } else {
        seg[sz + i].a = {-(ll)4e18, -1};
      }
      seg[sz + i].b = {-(ll)4e18, -1};
    }
    for (ll i = sz - 1; i >= 1; --i)
      seg[i] = merge(seg[i * 2], seg[i * 2 + 1]);
  }
  void push(ll i) {
    ll x = seg[i].lazy;
    if (x == 0)
      return;
    seg[i * 2].a.val += x;
    seg[i * 2].b.val += x;
    seg[i * 2].lazy += x;
    seg[i * 2 + 1].a.val += x;
    seg[i * 2 + 1].b.val += x;
    seg[i * 2 + 1].lazy += x;
    seg[i].lazy = 0;
  }
  void upd(ll i, ll l, ll r, ll a, ll b, ll w) {
    if (l > b || r < a)
      return;
    if (l >= a && r <= b) {
      seg[i].a.val += w;
      seg[i].b.val += w;
      seg[i].lazy += w;
      return;
    }
    push(i);
    ll mid = (l + r) / 2;
    upd(i * 2, l, mid, a, b, w);
    upd(i * 2 + 1, mid + 1, r, a, b, w);
    seg[i] = merge(seg[i * 2], seg[i * 2 + 1]);
  }
  void update_range(ll l, ll r, ll w) {
    if (l <= r)
      upd(1, 0, sz - 1, l, r, w);
  }
  void update_all(ll w) {
    upd(1, 0, sz - 1, 0, sz - 1, w);
  }
  ll ans() {
    return seg[1].a.val + seg[1].b.val;
  }
};

vector<SegC> segsC;
vector<ll> cent_node;
vector<ll> cent_id_of_node;
vector<vector<pair<ll, ll>>> affect;

ll build_centroid(ll root) {
  getsz(root, -1);
  ll c = getcent(root, -1, szt[root]);
  vector<ll> nodes;
  collect_nodes(c, -1, nodes);
  ll idx = (ll)segsC.size();
  cent_node.push_back(c);
  cent_id_of_node[c] = idx;
  segsC.emplace_back(SegC(c, nodes));
  deadc[c] = 1;
  for (auto [v, id] : adj_e[c]) {
    if (deadc[v])
      continue;
    build_centroid(v);
  }
  return idx;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cin >> n >> q >> w;
  edges.resize(n - 1);
  g.resize(n);
  wg.assign(n, {});
  adj_e.assign(n, {});
  for (ll i = 0; i < n - 1; ++i) {
    ll a, b, c;
    cin >> a >> b >> c;
    a--;
    b--;
    edges[i] = {a, b, c};
    g[a].push_back(b);
    g[b].push_back(a);
  }
  Seg seg;
  par[0] = -1;
  for (ll i = 0; i < n - 1; ++i) {
    auto& [a, b, c] = edges[i];
    if (par[b] != a)
      swap(a, b);
    seg.update(b, c);
  }
  wg.clear();
  wg.assign(n, {});
  adj_e.assign(n, {});
  for (ll i = 0; i < n - 1; ++i) {
    auto [a, b, c] = edges[i];
    wg[a].push_back({b, i});
    wg[b].push_back({a, i});
    adj_e[a].push_back({b, i});
    adj_e[b].push_back({a, i});
  }
  deadc.assign(n, 0);
  szt.assign(n, 0);
  cent_id_of_node.assign(n, -1);
  affect.assign(n - 1, {});
  build_centroid(0);
  for (ll ci = 0; ci < (ll)segsC.size(); ++ci) {
    ll c = cent_node[ci];
    for (ll i = 0; i < n - 1; ++i) {
      auto [a, b, wc] = edges[i];
      ll inside = (tin[c] >= tin[b] && tin[c] <= tout[b]) ? 1 : 0;
      affect[i].push_back({ci, inside});
    }
  }
  multiset<ll> ms;
  vector<ll> cur(segsC.size());
  for (ll i = 0; i < (ll)segsC.size(); ++i) {
    cur[i] = segsC[i].ans();
    ms.insert(cur[i]);
  }
  ll last = 0;
  while (q--) {
    ll d, e;
    cin >> d >> e;
    ll d1 = (d + last) % (n - 1);
    ll e1 = (e + last) % w;
    auto& [a, b, c] = edges[d1];
    ll dis = e1 - c;
    c = e1;
    for (auto pr : affect[d1]) {
      ll ci = pr.f;
      ll inside = pr.s;
      ms.erase(ms.find(cur[ci]));
      if (inside) {
        segsC[ci].update_all(dis);
        segsC[ci].update_range(tin[b], tout[b], -dis);
      } else {
        segsC[ci].update_range(tin[b], tout[b], dis);
      }
      cur[ci] = segsC[ci].ans();
      ms.insert(cur[ci]);
    }
    last = *ms.rbegin();
    cout << last << endl;
  }
}

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