Submission #944005

#	Time	Username	Problem	Language	Result	Execution time	Memory
944005		vjudge1	Dynamic Diameter (CEOI19_diameter)	C++17	31 / 100	1039 ms	11512 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];
  for (int i = 1; i < n; ++i) {
    cin >> a[i] >> b[i] >> c[i];
  }
  if (n <= 5000 && q <= 5000) {
    vector<pair<int, int>> g[n + 1];
    vector<vector<int>> dp(n + 1, vector<int> (3, 0));
    for (int i = 1; i < n; ++i) {
      g[a[i]].push_back({b[i], i});
      g[b[i]].push_back({a[i], i});
    }
    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 {
    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';
    }
  }
}

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