Submission #924798

#	Time	Username	Problem	Language	Result	Execution time	Memory
924798		Camillus	Dynamic Diameter (CEOI19_diameter)	C++17	100 / 100	1841 ms	134316 KiB

diameter

/// @author Camillus
#include "bits/stdc++.h"

using ll = long long;
using namespace std;

mt19937 rnd(228);

vector<pair<int, int>> g[100500];
int from[100500];
int to[100500];
ll w[100500];

int sz[100500];
bool mark[100500];

void dfs_sz(int u, int p = -1) {
    sz[u] = 1;
    for (auto [v, i] : g[u]) {
        if (v != p && !mark[v]) {
            dfs_sz(v, u);
            sz[u] += sz[v];
        }
    }
}

namespace detail {
    int component_size;
    int level;
    int centoid;
};

int get_centroid(int u, int p = -1) {
    for (auto [v, i] : g[u]) {
        if (v != p && !mark[v] && sz[v] * 2 > detail::component_size) {
            return get_centroid(v, u);
        }
    }
    return u;
}

int vertex_centroid[20][100500];
int tin[20][100500];
int tout[20][100500];
int timer[20];

namespace st {
    static constexpr int size = 1 << 17;

    struct node {
        ll max = 0;
        ll add = 0;
    } tree[20][size * 2 - 1];
} // namespace st

struct segment_tree {
    static constexpr int size = st::size;

    st::node *tree;

    segment_tree(int level) {
        tree = st::tree[level];
    }

    inline void apply(int x, ll v) const {
        tree[x].max += v;
        tree[x].add += v;
    }

    inline void push(int x) const {
        if (tree[x].add) {
            apply(x * 2 + 1, tree[x].add);
            apply(x * 2 + 2, tree[x].add);
            tree[x].add = 0;
        }
    }

    inline void pull(int x) const {
        tree[x].max = max(tree[x * 2 + 1].max, tree[x * 2 + 2].max);
    }

    inline void set(int i, ll v) const {
        int x = size + i - 1;
        tree[x].max = v;
        while (x) {
            x = (x - 1) / 2;
            pull(x);
        }
    }

    void add(int l, int r, ll v, int x = 0, int lx = 0, int rx = size) const {
        if (l >= rx || lx >= r) {
            return;
        }

        if (l <= lx && rx <= r) {
            apply(x, v);
            return;
        }

        push(x);

        add(l, r, v, x * 2 + 1, lx, (lx + rx) / 2);
        add(l, r, v, x * 2 + 2, (lx + rx) / 2, rx);

        pull(x);
    }

    ll get(int l, int r, int x = 0, int lx = 0, int rx = size) const {
        if (l <= lx && rx <= r) {
            return tree[x].max;
        }

        if (l >= rx || lx >= r) {
            return 0;
        }

        push(x);

        return max(
                get(l, r, x * 2 + 1, lx, (lx + rx) / 2),
                get(l, r, x * 2 + 2, (lx + rx) / 2, rx)
        );
    }
};


namespace st2 {
    static constexpr int size = 1 << 17;
    ll tree[size * 2 - 1];

    void set(int i, ll v) {
        int x = size + i - 1;
        tree[x] = v;

        while (x) {
            x = (x - 1) / 2;
            tree[x] = max(tree[x * 2 + 1], tree[x * 2 + 2]);
        }
    }

    ll get() {
        return tree[0];
    }
};

vector<int> centoid_children[100500];

vector<ll> C1[100500];
multiset<ll, greater<ll>> C2[100500];

ll get_centroid_diameter(int u) {
    if (C2[u].empty()) {
        return 0;
    } else if (C2[u].size() == 1) {
        return C1[u].back();
    } else {
        return *C2[u].begin() + *next(C2[u].begin());
    }
}

void update_cetroid_diameter(int u) {
    st2::set(u, get_centroid_diameter(u));
}

void dfs_centroid(int u, int p = -1, ll d = 0) {
    vertex_centroid[detail::level][u] = detail::centoid;

    bool is_leaf = true;

    for (auto [v, i] : g[u]) {
        if (v != p && !mark[v]) {
            dfs_centroid(v, u, d + w[i]);
            if (is_leaf) {
                tin[detail::level][u] = tin[detail::level][v];
            }
            tout[detail::level][u] = tout[detail::level][v];
            is_leaf = false;
        }
    }

    if (is_leaf) {
        tin[detail::level][u] = timer[detail::level]++;
        tout[detail::level][u] = timer[detail::level];
        segment_tree(detail::level).set(tin[detail::level][u], d);
    }
}

void dfs_main(int u, int l = 0) {
    detail::level = l;

    dfs_sz(u);
    detail::component_size = sz[u];

    u = get_centroid(u);
    detail::centoid = u;
    mark[u] = true;

    dfs_centroid(u);

    segment_tree ST(l);

    for (auto [v, i] : g[u]) {
        if (!mark[v]) {
            C1[u].push_back(ST.get(tin[l][v], tout[l][v]));
            C2[u].insert(C1[u].back());
            centoid_children[u].push_back(v);
            dfs_main(v, l + 1);
        }
    }

    update_cetroid_diameter(u);
}

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

    int n, q;
    cin >> n >> q;

    ll W;
    cin >> W;

    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v >> w[i];

        from[i] = u;
        to[i] = v;

        g[u].emplace_back(v, i);
        g[v].emplace_back(u, i);
    }

    dfs_main(1);

    ll last = 0;

    while (q--) {
        ll d, e;
        cin >> d >> e;

        d = (d + last) % (n - 1);
        e = (e + last) % W;

        int u = from[d];
        int v = to[d];

        ll change = e - w[d];
        w[d] = e;

        for (int l = 0; l < 20; l++) {
            if (!vertex_centroid[l][u] || vertex_centroid[l][u] != vertex_centroid[l][v]) {
                break;
            }

            int c = vertex_centroid[l][u];

            int L = max(tin[l][u], tin[l][v]);
            int R = min(tout[l][u], tout[l][v]);

            segment_tree ST(l);

            ST.add(L, R, change);

            auto it = upper_bound(centoid_children[c].begin(), centoid_children[c].end(), L, [&l](int L, int u) -> bool {
                return L < tin[l][u];
            });

            it = prev(it);

            int i = it - centoid_children[c].begin();
            int U = centoid_children[c][i];

            C2[c].erase(C2[c].find(C1[c][i]));
            C1[c][i] = ST.get(tin[l][U], tout[l][U]);
            C2[c].insert(C1[c][i]);

            update_cetroid_diameter(c);
        }

        last = st2::get();
        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