제출 #1276597

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1276597		MisterReaper	Dynamic Diameter (CEOI19_diameter)	C++20	49 / 100	5101 ms	234368 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 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);
    }
};

struct Item {
    int tim;
    std::map<int, int> id;
    std::vector<int> vrt, tin, tout, par, gpar;
    std::vector<i64> val;
    std::multiset<i64> overall;
    segtree seg;
    Item() {}
    void init(int n) {
        tim = 0;
        vrt.resize(n);
        tin.resize(n);
        tout.resize(n);
        par.resize(n, -1);
        seg.init(n);
        gpar.resize(n);
        val.resize(n);
    }
    i64 value() {
        return *overall.rbegin() + *++overall.rbegin();
    }
};

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) {
    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;
            itm.overall.emplace(0);
            itm.overall.emplace(0);
        } 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);
    }
    itm.tout[itm.id[v]] = itm.tim;
}

void decomp(int r) {
    debug("decomp", r);
    csiz(r, -1);
    int v = gcen(r, -1, siz[r]);
    debug(v);
    items[v].init(siz[r]);
    dfs(v, -1, v);
    debug("ok");
    act[v] = false;
    for (auto i : adj[v]) {
        int u = E[i][0] ^ E[i][1] ^ v;
        if (!act[u]) {
            continue;
        }
        decomp(u);
    }
}

std::multiset<i64> overall;

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];
            overall.extract(itm.value());
            itm.overall.extract(itm.val[pr]);
            itm.seg.modify(itm.tin[idu], itm.tout[idu] - 1, x);
            itm.overall.emplace(itm.val[pr] = itm.seg.get(itm.tin[pr], itm.tout[pr] - 1));
            overall.emplace(itm.value());
        } else {
            int pr = itm.gpar[idv];
            overall.extract(itm.value());
            itm.overall.extract(itm.val[pr]);
            itm.seg.modify(itm.tin[idv], itm.tout[idv] - 1, x);
            itm.overall.emplace(itm.val[pr] = itm.seg.get(itm.tin[pr], itm.tout[pr] - 1));
            overall.emplace(itm.value());
        }
    }
}

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

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

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

    for (int i = 0; i < N - 1; ++i) {
        add(i, C[i]);
    }
    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.rbegin();
        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