Submission #1276889

#	Time	Username	Problem	Language	Result	Execution time	Memory
1276889		MisterReaper	Dynamic Diameter (CEOI19_diameter)	C++20	100 / 100	239 ms	35192 KiB

diameter

// File diameter.cpp created on 07.10.2025 at 15:21:00
#include <bits/stdc++.h>

using i64 = long long;

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

constexpr int max_N = int(1E5) + 5;

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

int tim;
int tin[max_N], tout[max_N], par[max_N];
void dfs(int v) {
    tin[v] = tim++;
    for (auto i : adj[v]) {
        int u = E[i][0] ^ E[i][1] ^ v;
        if (u == par[v]) {
            continue;
        }
        par[u] = v;
        dfs(u);
    }
    tout[v] = tim++;
}

struct node {
    i64 sum = 0;
    i64 mind = 0;
    i64 maxd = 0;
    i64 maxlv = 0;
    i64 maxrv = 0;
    i64 maxlr = 0;
    node() {}
    node(i64 x) {
        sum = x;
        if (x >= 0) {
            mind = 0;
            maxd = x;
            maxlv = 0;
            maxrv = x;
            maxlr = x;
        } else {
            mind = x;
            maxd = 0;
            maxlv = - 2 * x;
            maxrv = - x;
            maxlr = - x;
        }
    }
    node shifted(i64 x) {
        node res;
        res.sum = sum + x;
        res.mind = mind + x;
        res.maxd = maxd + x;
        res.maxlv = maxlv - x;
        res.maxrv = maxrv - x;
        res.maxlr = maxlr;
        return res;
    }
};
node operator+ (node lhs, node rhs) {
    rhs = rhs.shifted(lhs.sum);
    node res;
    res.sum = rhs.sum;
    res.mind = std::min(lhs.mind, rhs.mind);
    res.maxd = std::max(lhs.maxd, rhs.maxd);
    res.maxlv = std::max({lhs.maxlv, rhs.maxlv, lhs.maxd - 2 * rhs.mind});
    res.maxrv = std::max({lhs.maxrv, rhs.maxrv, - 2 * lhs.mind + rhs.maxd});
    res.maxlr = std::max({lhs.maxlr, rhs.maxlr, lhs.maxlv + rhs.maxd, lhs.maxd + rhs.maxrv});
    return res;
}

#define def int mid = (l + r) >> 1, lv = v + 1, rv = v + ((mid - l + 1) << 1)

struct segtree {
    int n;
    std::vector<node> tree;
    segtree(int n_) : n(n_), tree(n << 1) {}
    void modify(int v, int l, int r, int p, i64 x) {
        if (l == r) {
            tree[v] = {x};
            return;
        }
        def;
        if (p <= mid) {
            modify(lv, l, mid, p, x);
        } else {
            modify(rv, mid + 1, r, p, x);
        }
        tree[v] = tree[lv] + tree[rv];
    }
    void modify(int p, i64 x) {
        modify(0, 0, n - 1, p, x);
    }
    node get(int v, int l, int r, int ql, int qr) {
        if (l == ql && qr == r) {
            return tree[v];
        }
        def;
        if (qr <= mid) {
            return get(lv, l, mid, ql, qr);
        } else if (mid + 1 <= ql) {
            return get(rv, mid + 1, r, ql, qr);
        } else {
            return get(lv, l, mid, ql, mid)
                + get(rv, mid + 1, r, mid + 1, qr);
        }
    }
    node get(int l, int r) {
        return get(0, 0, n - 1, l, r);
    }
    void debug_(int v, int l, int r) {
        debug(v, l, r);
        debug(tree[v].sum, tree[v].mind, tree[v].maxd, tree[v].maxlv, tree[v].maxrv, tree[v].maxlr);
        if (l == r) {
            return;
        }
        def;
        debug_(lv, l, mid);
        debug_(rv, mid + 1, r);
    }
    void debug_() {
        debug_(0, 0, n - 1);
    }
};

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

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

    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);

    for (int i = 0; i < N - 1; ++i) {
        auto&[u, v] = E[i];
        if (par[u] == v) {
            std::swap(u, v);
        }
    }

    segtree seg(2 * N - 2);
    for (int i = 0; i < N - 1; ++i) {
        seg.modify(tin[E[i][1]] - 1, C[i]);
        seg.modify(tout[E[i][1]] - 1, -C[i]);
    }

    auto debug_ = [&]() -> void {
        seg.debug_();
        debug();
    };

    i64 ans = 0;
    while (Q--) {
        i64 I, X;
        std::cin >> I >> X;
        I = (I + ans) % (N - 1);
        X = (X + ans) % W;
        seg.modify(tin[E[I][1]] - 1, X);
        seg.modify(tout[E[I][1]] - 1, -X);
        C[I] = X;
        // debug_();
        ans = seg.tree[0].maxlr;
        std::cout << ans << '\n';
    }

    return 0;
}

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