Submission #1276605

#	Time	Username	Problem	Language	Result	Execution time	Memory
1276605		MisterReaper	Dynamic Diameter (CEOI19_diameter)	C++20	100 / 100	4172 ms	278140 KiB

diameter

// File diameter.cpp created on 06.10.2025 at 09:23:46
#pragma GCC optimize("unroll-loops,O3")
#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;
i64 C[max_N];
std::array<int, 2> E[max_N];
std::vector<int> adj[max_N];

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

struct segtree {
    int n;
    std::vector<i64> tree, lz;
    segtree() {}
    void init(int n_) {
        n = n_;
        tree.resize(n << 1);
        lz.resize(n << 1);
    }
    void build(int v, int l, int r, std::vector<i64>& vec) {
        if (l == r) {
            tree[v] = vec[l];
            return;
        }
        def;
        build(lv, l, mid, vec);
        build(rv, mid + 1, r, vec);
        tree[v] = std::max(tree[lv], tree[rv]);
    }
    void modify_node(int v, i64 x) {
        tree[v] += x;
        lz[v] += x;
    }
    void push(int v, int l, int r) {
        def;
        modify_node(lv, lz[v]);
        modify_node(rv, lz[v]);
        lz[v] = 0;
    }
    void modify(int v, int l, int r, int ql, int qr, i64 x) {
        if (ql == l && r == qr) {
            modify_node(v, x);
            return;
        }
        def;
        push(v, l, r);
        if (qr <= mid) {
            modify(lv, l, mid, ql, qr, x);
        } else if (mid + 1 <= ql) {
            modify(rv, mid + 1, r, ql, qr, x);
        } else {
            modify(lv, l, mid, ql, mid, x);
            modify(rv, mid + 1, r, mid + 1, qr, x);
        }
        tree[v] = std::max(tree[lv], tree[rv]);
    }
    void modify(int l, int r, i64 x) {
        modify(0, 0, n - 1, l, r, x);
    }
    i64 get(int v, int l, int r, int ql, int qr) {
        if (ql == l && r == qr) {
            return tree[v];
        }
        def;
        push(v, l, r);
        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 std::max(get(lv, l, mid, ql, mid),
                            get(rv, mid + 1, r, mid + 1, qr));
        }
    }
    i64 get(int l, int r) {
        return get(0, 0, n - 1, l, r);
    }
};

std::pair<i64, i64> operator+ (std::pair<i64, i64>& lhs, std::pair<i64, i64>& rhs) {
    std::pair<i64, i64> res;
    if (lhs.first < rhs.first) {
        res.first = rhs.first;
        res.second = std::max(lhs.first, rhs.second);
    } else {
        res.first = lhs.first;
        res.second = std::max(rhs.first, lhs.second);
    }
    return res;
}

struct multiset_twice {
    int n;
    std::vector<std::pair<i64, i64>> tree;
    multiset_twice() {}
    void init(int n_) {
        n = n_;
        tree.resize(n << 1);
    }
    void modify(int v, int l, int r, int p, i64 x) {
        if (l == r) {
            tree[v] = {x, 0};
            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);
    }
};

struct multiset_once {
    int n;
    i64 tree[max_N << 1];
    multiset_once() {}
    void init(int n_) {
        n = n_;
    }
    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] = std::max(tree[lv], tree[rv]);
    }
    void modify(int p, i64 x) {
        modify(0, 0, n - 1, p, x);
    }
};

struct Item {
    int tim;
    std::map<int, int> id;
    std::vector<int> vrt, tin, tout, par, gpar;
    multiset_twice overall;
    segtree seg;
    Item() {}
    void init(int n) {
        tim = 0;
        vrt.resize(n);
        tin.resize(n);
        tout.resize(n);
        par.resize(n, -1);
        overall.init(n + 1);
        seg.init(n);
        gpar.resize(n);
    }
    i64 value() {
        return overall.tree[0].first + overall.tree[0].second;
    }
};

int act[max_N];
int siz[max_N];
Item items[max_N];
std::vector<int> cedg[max_N];

void csiz(int v, int pr) {
    siz[v] = 1;
    for (auto i : adj[v]) {
        int u = E[i][0] ^ E[i][1] ^ v;
        if (!act[u] || u == pr) {
            continue;
        }
        csiz(u, v);
        siz[v] += siz[u];
    }
}

int gcen(int v, int pr, int osiz) {
    for (auto i : adj[v]) {
        int u = E[i][0] ^ E[i][1] ^ v;
        if (!act[u] || u == pr) {
            continue;
        }
        if (siz[u] * 2 > osiz) {
            return gcen(u, v, osiz);
        }
    }
    return v;
}

void dfs(int v, int pr, int root, std::vector<i64>& pre) {
    debug(v, pr, root);
    Item& itm = items[root];
    itm.vrt[itm.tim] = v;
    itm.id[v] = itm.tim;
    itm.tin[itm.tim] = itm.tim;
    if (v == root) {
        itm.gpar[itm.tim] = itm.tim;
    } else {
        if (pr == root) {
            itm.gpar[itm.tim] = itm.tim;
        } else {
            itm.gpar[itm.tim] = itm.gpar[itm.id[pr]];
        }
    }
    itm.tim++;
    for (auto i : adj[v]) {
        int u = E[i][0] ^ E[i][1] ^ v;
        if (!act[u] || u == pr) {
            continue;
        }
        cedg[i].emplace_back(root);
        dfs(u, v, root, pre);
        pre[itm.tin[itm.id[u]]] += C[i];
        pre[itm.tout[itm.id[u]]] -= C[i];
    }
    itm.tout[itm.id[v]] = itm.tim;
}

multiset_once overall;

void decomp(int r) {
    debug("decomp", r);
    csiz(r, -1);
    int v = gcen(r, -1, siz[r]);
    debug(v);
    items[v].init(siz[r]);
    std::vector<i64> pre(siz[r] + 1);
    dfs(v, -1, v, pre);
    for (int i = 1; i <= siz[r]; ++i) {
        pre[i] += pre[i - 1];
    }
    debug(pre);
    items[v].seg.build(0, 0, siz[r] - 1, pre);
    debug("ok");
    act[v] = false;
    for (auto i : adj[v]) {
        int u = E[i][0] ^ E[i][1] ^ v;
        if (!act[u]) {
            continue;
        }
        int idu = items[v].id[u];
        items[v].overall.modify(idu, items[v].seg.get(items[v].tin[idu], items[v].tout[idu] - 1));
        decomp(u);
    }
    overall.modify(v, items[v].value());
}

void add(int ei, i64 x) {
    auto[u, v] = E[ei];
    for (auto cr : cedg[ei]) {
        Item& itm = items[cr];
        int idu = itm.id[u];
        int idv = itm.id[v];
        if (idu > idv) {
            int pr = itm.gpar[idu];
            itm.seg.modify(itm.tin[idu], itm.tout[idu] - 1, x);
            itm.overall.modify(pr, itm.seg.get(itm.tin[pr], itm.tout[pr] - 1));
            overall.modify(cr, itm.value());
        } else {
            int pr = itm.gpar[idv];
            itm.seg.modify(itm.tin[idv], itm.tout[idv] - 1, x);
            itm.overall.modify(pr, itm.seg.get(itm.tin[pr], itm.tout[pr] - 1));
            overall.modify(cr, itm.value());
        }
    }
}

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

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

    overall.init(N);
    std::memset(act, 1, sizeof(act));

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

    decomp(0);
    debug("decompose is successfull");

    debug("add is successfull");

    i64 last = 0;
    while (Q--) {
        int I;
        i64 X;
        std::cin >> I >> X;
        I = (I + last) % (N - 1);
        X = (X + last) % W;
        add(I, X - C[I]);
        C[I] = X;
        last = overall.tree[0];
        std::cout << last << '\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