Submission #1276577

#	Time	Username	Problem	Language	Result	Execution time	Memory
1276577		MisterReaper	Dynamic Diameter (CEOI19_diameter)	C++20	Compilation error	0 ms	0 KiB

diameter

// File diameter.cpp created on 06.10.2025 at 09:23:46
#pragma GCC optimize("unroll-loops,O3")
#pragma GCC target("avx2,bmi,bmi2")
#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;

#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;
    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;
    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() {
        if (overall.empty()) {
            return 0;
        } else if (int(overall.size()) == 1) {
            return *overall.rbegin();
        } else {
            return *overall.rbegin() + *++overall.rbegin();
        }
    }
};

std::vector<int> act, siz;
std::vector<Item> items;
std::vector<std::vector<int>> cedg;

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.id[v]] = itm.tim++;
    if (v == root) {
        itm.gpar[itm.id[v]] = itm.id[v];
    } else {
        if (pr == root) {
            itm.gpar[itm.id[v]] = itm.id[v];
            itm.overall.emplace(0);
        } else {
            itm.gpar[itm.id[v]] = itm.gpar[itm.id[pr]];
        }
    }
    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;

    adj.resize(N);
    E.resize(N - 1);
    C.resize(N - 1);
    items.resize(N);
    cedg.resize(N - 1);
    siz.resize(N);
    act.resize(N, true);

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

Compilation message (stderr)

In file included from /usr/include/c++/13/string:43,
                 from /usr/include/c++/13/bitset:52,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:52,
                 from diameter.cpp:4:
/usr/include/c++/13/bits/allocator.h: In destructor 'constexpr std::_Vector_base<long long int, std::allocator<long long int> >::_Vector_impl::~_Vector_impl()':
/usr/include/c++/13/bits/allocator.h:184:7: error: inlining failed in call to 'always_inline' 'constexpr std::allocator< <template-parameter-1-1> >::~allocator() noexcept [with _Tp = long long int]': target specific option mismatch
  184 |       ~allocator() _GLIBCXX_NOTHROW { }
      |       ^
In file included from /usr/include/c++/13/vector:66,
                 from /usr/include/c++/13/functional:64,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:53:
/usr/include/c++/13/bits/stl_vector.h:133:14: note: called from here
  133 |       struct _Vector_impl
      |              ^~~~~~~~~~~~