Submission #1277871

#	Time	Username	Problem	Language	Result	Execution time	Memory
1277871		LIA	Dynamic Diameter (CEOI19_diameter)	C++17	7 / 100	169 ms	7344 KiB

diameter

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define f first
#define s second
const ll inf = 1e10;

static inline ll diameter(const multiset<ll>& S) {
  if (S.size() == 1)
    return *S.rbegin();
  auto it1 = prev(S.end());
  ll a = *it1;
  auto it2 = prev(it1);
  ll b = *it2;
  return a + b;
}

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

  ll n, q, wlim;
  cin >> n >> q >> wlim;

  vector<ll> wts(n - 1);
  multiset<ll> S;
  for (ll i = 0; i < n - 1; ++i) {
    ll a, b, c;
    cin >> a >> b >> c;
    wts[i] = c;
    S.insert(c);
  }

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

    auto it = S.find(wts[d1]);
    S.erase(it);
    wts[d1] = e1;
    S.insert(e1);

    ll ans;
    if (n == 2) {
      ans = *S.rbegin();
    } else {
      ans = diameter(S);
    }

    cout << ans << '\n';
    last = ans;
  }
}

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