Submission #503140

#	Time	Username	Problem	Language	Result	Execution time	Memory
503140		BERNARB01	Dynamic Diameter (CEOI19_diameter)	C++17	24 / 100	5102 ms	11348 KiB

diameter

#include <bits/stdc++.h>

using namespace std;

struct edge {
  int from, to;
  long long w;
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, q;
  long long md;
  cin >> n >> q >> md;
  vector<edge> ed(n + n);
  vector<vector<int>> g(n);
  for (int i = 0; i < n - 1; i++) {
    int u, v;
    long long w;
    cin >> u >> v >> w;
    --u; --v;
    ed[i] = {u, v, w};
    ed[i + n - 1] = {v, u, w};
    g[u].emplace_back(i);
    g[v].emplace_back(i + n - 1);
  }
  pair<long long, int> best_dia;
  function<void(int, int, long long)> calc_dia = [&](int v, int pr, long long dist) {
    best_dia = max(best_dia, make_pair(dist, v));
    for (int e : g[v]) {
      if (ed[e].to == pr) {
        continue;
      }
      calc_dia(ed[e].to, v, dist + ed[e].w);
    }
  };
  long long last = 0;
  for (int t = 0; t < q; t++) {
    int dd;
    long long ee;
    cin >> dd >> ee;
    int d = ((long long) dd + last) % (n - 1);
    long long w = (ee + last) % md;
    ed[d].w = w;
    ed[d + n - 1].w = w;
    best_dia = make_pair(0, 0);
    calc_dia(0, -1, 0);
    calc_dia(best_dia.second, -1, 0);
    last = best_dia.first;
    cout << last << '\n';
  }
  return 0;
}

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