Submission #1277868

#	Time	Username	Problem	Language	Result	Execution time	Memory
1277868		LIA	Dynamic Diameter (CEOI19_diameter)	C++17	42 / 100	5093 ms	20220 KiB

diameter

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define f first
#define s second
const ll inf = 4e18;
#define vll vector<ll>
#define pll pair<ll, ll>
ll n, q, w1;
// struct Seg {
//   ll sz = 1;
//   vector<pair<ll, ll>> seg;
//   vll segans;
//   Seg(ll n) {
//     for (; sz < n; sz *= 2)
//       ;
//     seg.resize(2 * sz, {-inf, -inf});
//     segans.resize(2 * sz, -inf);
//   }
//   void update(ll pos, ll w) {
//     pos += sz;
//     seg[pos] = {w, -inf};
//     segans[pos] = w;
//     for (pos /= 2; pos > 0; pos /= 2) {
//       seg[pos] = {max(seg[pos * 2].first, seg[pos * 2 + 1].first), -inf};
//       segans[pos] = max(segans[pos * 2], segans[pos * 2 + 1]);
//     }
//   }
// };
vector<pll> par;
vector<vector<pll>> g;
multiset<ll, greater<ll>> s;
vector<pll> longest;
vll ansi;
void dfs(ll node, ll pari) {
  for (auto [it, c] : g[node]) {
    if (it != pari) {
      par[it] = {node, c};
      dfs(it, node);
    }
  }
}

void update(ll node, ll neww) {
  if (node != 1) {
    for (auto& [nd, w] : g[par[node].first]) {
      if (nd == node)
        w = neww;
    }
    for (auto& [nd, w] : g[node]) {
      if (nd == par[node].first)
        w = neww;
    }
  }
  if (node != 1)
    node = par[node].first;
  for (;;) {
    s.erase(s.find(ansi[node]));
    vector<ll> v;
    for (auto [it, c] : g[node])
      if (it != par[node].first) {
        v.push_back(max(longest[it].first, longest[it].second) + c);
      }
    sort(v.begin(), v.end(), greater<ll>());
    if (v.empty())
      longest[node] = {0, 0};
    else if ((ll)v.size() == 1)
      longest[node] = {0, v[0]};
    else
      longest[node] = {v[1], v[0]};
    ansi[node] = longest[node].first + longest[node].second;
    s.insert(ansi[node]);
    if (node == 1)
      break;
    node = par[node].first;
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  cin >> n >> q >> w1;
  par.resize(n + 1);
  g.assign(n + 1, {});
  ansi.assign(n + 1, 0);
  longest.assign(n + 1, {0, 0});

  vector<tuple<ll, ll, ll>> edges(n - 1);
  for (ll i = 0; i < n - 1; ++i) {
    ll a, b, c;
    cin >> a >> b >> c;
    edges[i] = {a, b, c};
    g[a].push_back({b, c});
    g[b].push_back({a, c});
  }

  dfs(1, 0);

  vector<int> order;
  order.reserve(n);
  {
    vector<int> st = {1};
    vector<int> parent(n + 1, 0);
    while (!st.empty()) {
      int u = st.back();
      st.pop_back();
      order.push_back(u);
      for (auto [v, w] : g[u])
        if (v != parent[u]) {
          parent[v] = u;
          st.push_back(v);
        }
    }
    reverse(order.begin(), order.end());
  }

  for (int u : order) {
    vector<ll> v;
    for (auto [to, w] : g[u])
      if (to != par[u].first) {
        v.push_back(max(longest[to].first, longest[to].second) + w);
      }
    sort(v.begin(), v.end(), greater<ll>());
    if (v.empty())
      longest[u] = {0, 0};
    else if ((ll)v.size() == 1)
      longest[u] = {0, v[0]};
    else
      longest[u] = {v[1], v[0]};
    ansi[u] = longest[u].first + longest[u].second;
    s.insert(ansi[u]);
  }

  ll last = 0;
  while (q--) {
    ll d, e;
    cin >> d >> e;
    ll d1 = (d + last) % (n - 1);
    ll e1 = (e + last) % w1;

    ll a = get<0>(edges[d1]);
    ll b = get<1>(edges[d1]);
    ll node = (par[a].first == b ? a : b);
    update(node, e1);

    last = max(0LL, *s.begin());
    cout << last << '\n';
  }
}

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