Submission #689742

#	Time	Username	Problem	Language	Result	Execution time	Memory
689742		overwatch9	Dynamic Diameter (CEOI19_diameter)	C++17	7 / 100	426 ms	12064 KiB

diameter

// subtask3
#include <iostream>
#include <set>
using namespace std;
using ll = long long;
const int MAX_N = 1e5;
struct edge {
    int a, b;
    ll w;
};
edge edges[MAX_N];
int main() {
    int N, Q;
    ll W;
    cin >> N >> Q >> W;
    multiset <ll> weights;
    for (int i = 0; i < N-1; i++) {
        int a, b;
        ll w;
        cin >> a >> b >> w;
        edge tp;
        tp.a = a;
        tp.b = b;
        tp.w = w;
        edges[i] = tp;
        weights.insert(w);
    }
    ll last = 0;
    while (Q--) {
        ll d, e;
        cin >> d >> e;
        d = (d + last) % (N-1);
        e = (e + last) % (W);
        ll old_weight = edges[d].w;
        weights.erase(weights.find(old_weight));
        weights.insert(e);
        edges[d].w = e;
        last = *weights.rbegin();
        if (weights.size() >= 2)
            last += *(--(--weights.end()));
        cout << last << '\n';
    }
}

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