Submission #944028

#	Time	Username	Problem	Language	Result	Execution time	Memory
944028		vjudge1	Dynamic Diameter (CEOI19_diameter)	C++17	49 / 100	5027 ms	22220 KiB

diameter

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define all(x) x.begin(), x.end()
#define size(x) (int)x.size()

template<class S, class T>
bool chmin(S &a, const T &b) {
  return a > b ? (a = b) == b : false;
}
template<class S, class T>
bool chmax(S &a, const T &b) {
  return a < b ? (a = b) == b : false;
}

signed main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int n, q, w;
  cin >> n >> q >> w;
  int a[n], b[n], c[n];
  vector<pair<int, int>> g[n + 1];
  for (int i = 1; i < n; ++i) {
    cin >> a[i] >> b[i] >> c[i];
    g[a[i]].push_back({b[i], i});
    g[b[i]].push_back({a[i], i});
  }
  if (n <= 5000 && q <= 5000) {
    vector<vector<int>> dp(n + 1, vector<int> (3, 0));
    function<void(int, int)> dfs = [&](int v, int p) {
      dp[v][0] = dp[v][1] = dp[v][2] = 0;
      int max1 = 0, max2 = 0;
      for (auto [to, idx] : g[v]) {
        int cost = c[idx];
        if (to != p) {
          dfs(to, v);
          chmax(dp[v][0], dp[to][0]);
          chmax(dp[v][0], dp[to][1] + cost);
          chmax(dp[v][0], dp[to][2]);
          chmax(dp[v][1], dp[to][1] + cost);
          if (max1 < dp[to][1] + cost) {
            chmax(max2, max1);
            max1 = dp[to][1] + cost;
          } else chmax(max2, dp[to][1] + cost);
        }
      }
      dp[v][2] = max1 + max2;
    };
    int last = 0;
    while (q--) {
      int d, e; cin >> d >> e;
      d = (d + last) % (n - 1);
      e = (e + last) % w;
      d++;
      c[d] = e;
      dfs(1, -1);
      last = max({dp[1][0], dp[1][1], dp[1][2]});
      cout << last << '\n';
    }
  } else if (size(g[1]) == n - 1) {
    multiset<int> st;
    for (int i = 1; i < n; ++i) {
      st.insert(c[i]);
    }
    int last = 0;
    while (q--) {
      int d, e; cin >> d >> e;
      d = (d + last) % (n - 1);
      e = (e + last) % w;
      d++;
      st.erase(st.find(c[d]));
      st.insert(e);
      c[d] = e;
      if (size(st) == 1) {
        last = *st.rbegin();
      } else {
        int v = *st.rbegin();
        st.erase(--st.end());
        last = v + *st.rbegin();
        st.insert(v);
      }
      cout << last << '\n';
    }
  } else {
    vector<int> parent(n + 1, -1);
    function<void(int, int)> count_parents = [&](int v, int p) {
      parent[v] = p;
      for (auto [to, idx] : g[v]) {
        if (to != p) {
          count_parents(to, v);
        }
      }
    };
    count_parents(1, -1);
    vector<vector<int>> dp(n + 1, vector<int> (3, 0));
    function<void(int, int)> count_dp = [&](int v, int p) {
      dp[v][0] = dp[v][1] = dp[v][2] = 0;
      int max1 = 0, max2 = 0;
      for (auto [to, idx] : g[v]) {
        int cost = c[idx];
        if (to != p) {
          count_dp(to, v);
          chmax(dp[v][0], dp[to][0]);
          chmax(dp[v][0], dp[to][1] + cost);
          chmax(dp[v][0], dp[to][2]);
          chmax(dp[v][1], dp[to][1] + cost);
          if (max1 < dp[to][1] + cost) {
            chmax(max2, max1);
            max1 = dp[to][1] + cost;
          } else chmax(max2, dp[to][1] + cost);
        }
      }
      dp[v][2] = max1 + max2;
    };
    count_dp(1, -1);
    function<void(int)> upd = [&](int v) {
      if (v == -1) return;
      dp[v][0] = dp[v][1] = dp[v][2] = 0;
      int max1 = 0, max2 = 0;
      for (auto [to, idx] : g[v]) {
        int cost = c[idx];
        if (to != parent[v]) {
          chmax(dp[v][0], dp[to][0]);
          chmax(dp[v][0], dp[to][1] + cost);
          chmax(dp[v][0], dp[to][2]);
          chmax(dp[v][1], dp[to][1] + cost);
          if (max1 < dp[to][1] + cost) {
            chmax(max2, max1);
            max1 = dp[to][1] + cost;
          } else chmax(max2, dp[to][1] + cost);
        }
      }
      dp[v][2] = max1 + max2;
      upd(parent[v]);
    };
    int last = 0;
    while (q--) {
      int d, e; cin >> d >> e;
      d = (d + last) % (n - 1);
      e = (e + last) % w;
      d++;
      c[d] = e;
      if (parent[a[d]] == b[d]) upd(b[d]);
      else upd(a[d]);
      last = max({dp[1][0], dp[1][1], dp[1][2]});
      cout << last << '\n';
    }
  }
}

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