Submission #689742

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
689742	2023-01-29T09:13:57 Z	overwatch9	Dynamic Diameter (CEOI19_diameter)	C++17	7 / 100	426 ms	12064 KB

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.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	0 ms	212 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	0 ms	212 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #3
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	6 ms	212 KB	Output is correct
4	Correct	35 ms	340 KB	Output is correct
5	Correct	195 ms	692 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	1 ms	340 KB	Output is correct
8	Correct	2 ms	340 KB	Output is correct
9	Correct	5 ms	340 KB	Output is correct
10	Correct	43 ms	520 KB	Output is correct
11	Correct	188 ms	704 KB	Output is correct
12	Correct	4 ms	596 KB	Output is correct
13	Correct	5 ms	576 KB	Output is correct
14	Correct	8 ms	580 KB	Output is correct
15	Correct	43 ms	936 KB	Output is correct
16	Correct	199 ms	2220 KB	Output is correct
17	Correct	91 ms	7716 KB	Output is correct
18	Correct	90 ms	7684 KB	Output is correct
19	Correct	98 ms	7664 KB	Output is correct
20	Correct	147 ms	7952 KB	Output is correct
21	Correct	344 ms	9424 KB	Output is correct