Submission #597141

#	Time	Username	Problem	Language	Result	Execution time	Memory
597141		Valaki2	Dynamic Diameter (CEOI19_diameter)	C++14	18 / 100	668 ms	10604 KiB

diameter

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define pb push_back

const int maxn = 1e5;

struct edge {
    int to, wei;
    edge() : to(0), wei(0) {}
    edge(int to_, int wei_) :
        to(to_), wei(wei_) {}
};

int n, q, w;
vector<int> par_of;
vector<int> wei;
vector<int> best_dist;
vector<int> ans;
multiset<int> m;

void upd_ans(int cur) {
    if(m.find(ans[cur]) != m.end()) {
        m.erase(m.find(ans[cur]));
    }
    ans[cur] = wei[2 * cur] + best_dist[2 * cur] + wei[2 * cur + 1] + best_dist[2 * cur + 1];
    m.insert(ans[cur]);
}

int query(int cur) {
    int res = 0;
    while(cur > 0) {
        best_dist[cur] = max(best_dist[2 * cur] + wei[2 * cur], best_dist[2 * cur + 1] + wei[2 * cur + 1]);
        upd_ans(cur);
        cur /= 2;
    }
    res = *m.rbegin();
    return res;
}

void calc_best_dist(int cur) {
    if(cur > n) {
        return;
    }
    calc_best_dist(2 * cur);
    calc_best_dist(2 * cur + 1);
    best_dist[cur] = max(best_dist[2 * cur] + wei[2 * cur], best_dist[2 * cur + 1] + wei[2 * cur + 1]);
}

void solve() {
    cin >> n >> q >> w;
    par_of.assign(n - 1, 0);
    wei.assign(1 + 2 * n + 1, 0);
    best_dist.assign(1 + 2 * n + 1, 0);
    ans.assign(1 + n, 0);
    for(int i = 0; i < n - 1; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        if(a > b) {
            swap(a, b);
        }
        par_of[i] = b;
        wei[b] = c;
    }
    calc_best_dist(1);
    for(int i = 1; i <= n; i++) {
        upd_ans(i);
    }
    int last = 0;
    while(q--) {
        int d, e;
        cin >> d >> e;
        d = (d + last) % (n - 1);
        e = (e + last) % w;
        // ----- changable -----
        wei[par_of[d]] = e;
        int result = query(par_of[d] / 2);
        // ----- changable -----
        cout << result << "\n";
        last = result;
    }
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}

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