Submission #1276560

#	Time	Username	Problem	Language	Result	Execution time	Memory
1276560		MisterReaper	Dynamic Diameter (CEOI19_diameter)	C++20	49 / 100	5088 ms	31188 KiB

diameter

// File diameter.cpp created on 06.10.2025 at 09:23:46
#include <bits/stdc++.h>

using i64 = long long;

#ifdef DEBUG 
    #include "/home/ahmetalp/Desktop/Workplace/debug.h"
#else
    #define debug(...) void(23)
#endif

int N, Q;
i64 W;
std::vector<i64> C;
std::vector<std::array<int, 2>> E;
std::vector<std::vector<int>> adj;

std::vector<int> par, epar;
std::vector<std::multiset<i64>> vals;
std::multiset<i64> overall;

i64 get_max(std::multiset<i64>& mset) {
    if (mset.empty()) {
        return 0;
    }
    return *mset.rbegin();
}

i64 cost(std::multiset<i64>& mset) {
    if (mset.empty()) {
        return 0;
    }
    if (mset.size() == 1) {
        return *mset.rbegin();
    }
    return *mset.rbegin() + *++mset.rbegin();
}

void dfs(int v) {
    vals[v].emplace(0);
    for (auto i : adj[v]) {
        int u = E[i][0] ^ E[i][1] ^ v;
        adj[u].erase(std::find(adj[u].begin(), adj[u].end(), i));
        par[u] = v;
        epar[u] = i;
        dfs(u);
        vals[v].emplace(get_max(vals[u]) + C[i]);
    }
    overall.emplace(cost(vals[v]));
}

void del(int v) {
    std::vector<int> p {v};
    while (v != 0) {
        v = par[v];
        p.emplace_back(v);
    }
    std::reverse(p.begin(), p.end());
    for (int i = 0; i < int(p.size()); ++i) {
        int v = p[i];
        overall.extract(cost(vals[v]));
        if (i + 1 == int(p.size())) {
            vals[v].extract(0);
        } else {
            int u = p[i + 1];
            vals[v].extract(get_max(vals[u]) + C[epar[u]]);
        }
    }
}

void add(int v) {
    std::vector<int> p {v};
    while (v != 0) {
        v = par[v];
        p.emplace_back(v);
    }
    vals[v].emplace(0);
    for (int i = 0; i < int(p.size()); ++i) {
        int v = p[i];
        overall.emplace(cost(vals[v]));
        if (i + 1 != int(p.size())) {
            int u = p[i + 1];
            vals[u].emplace(get_max(vals[v]) + C[epar[v]]);
        }
    }
}

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

    std::cin >> N >> Q >> W;

    adj.resize(N);
    par.resize(N, -1);
    epar.resize(N, -1);
    E.resize(N - 1);
    C.resize(N - 1);
    vals.resize(N);

    for (int i = 0; i < N - 1; ++i) {
        std::cin >> E[i][0] >> E[i][1] >> C[i];
        --E[i][0], --E[i][1];
        adj[E[i][0]].emplace_back(i);
        adj[E[i][1]].emplace_back(i);
    }

    dfs(0);

    i64 last = 0;
    while (Q--) {
        int I;
        i64 X;
        std::cin >> I >> X;
        I = (I + last) % (N - 1);
        X = (X + last) % W;
        auto[u, v] = E[I];
        if (par[u] == v) {
            std::swap(u, v);
        }
        del(v);
        C[I] = X;
        add(v);
        last = get_max(overall);
        std::cout << last << '\n';
    }

    return 0;
}

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