제출 #1305930

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1305930		maxcruickshanks	Dynamic Diameter (CEOI19_diameter)	C++20	100 / 100	2761 ms	311532 KiB

diameter

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
#define fi first
#define se second
#define pb push_back
typedef long long ll;
typedef array<ll, 2> pi;

#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC target ("avx2")

struct node {
    int orig;
    ll mx, lz;
};
node merge(node l, node r) {
    if (l.mx > r.mx) { return l; }
    else { return r; }
}

// gemini segment tree b/c recursive is too slow...
struct segment_tree {
    int N, S, H;
    vector<node> seg;

    segment_tree(vector<int> &order, vector<ll> &dist) : N{int(order.size() + 2)}, H{0} {
        S = 1;
        while (S < N) { S <<= 1, H++; }
        seg.assign(2 * S, {.orig = -1});
        for (int i = 0; i < order.size(); ++i) {
            seg[S + i] = {order[i], dist[i], 0};
        }
        for (int rt = S - 1; rt > 0; --rt) {
            seg[rt] = merge(seg[2 * rt], seg[2 * rt + 1]);
        }
    }

    void apply(int rt, ll val) {
        seg[rt].mx += val;
        seg[rt].lz += val;
    }

    void build(int rt) {
        while (rt > 1) {
            rt >>= 1;
            node res = merge(seg[2 * rt], seg[2 * rt + 1]);
            seg[rt].mx = res.mx + seg[rt].lz;
            seg[rt].orig = res.orig;
        }
    }

    void push(int start_rt) {
        for (int lvl = H; lvl > 0; --lvl) {
            int rt = start_rt >> lvl;
            if (seg[rt].lz) {
                apply(2 * rt, seg[rt].lz);
                apply(2 * rt + 1, seg[rt].lz);
                seg[rt].lz = 0;
            }
        }
    }

    void update(int l, int r, ll delta) {
        if (l > r) { return; }
        l += S; r += S;
        int sl = l, sr = r;
        push(sl); push(sr);
        for (; l <= r; l >>= 1, r >>= 1) {
            if (l & 1) apply(l++, delta);
            if (!(r & 1)) apply(r--, delta);
        }
        build(sl); build(sr);
    }

    node query(int l, int r) {
        if (l > r) { return {.orig = -1, .mx=0}; }
        l += S; r += S;
        push(l); push(r);
        node resl = {0,0,0}, resr = {0,0,0};
        bool setl = false, setr = false;
        for (; l <= r; l >>= 1, r >>= 1) {
            if (l & 1) {
                resl = setl ? merge(resl, seg[l++]) : seg[l++];
                setl = true;
            }
            if (!(r & 1)) {
                resr = setr ? merge(seg[r--], resr) : seg[r--];
                setr = true;
            }
        }
        if (!setl) return resr;
        if (!setr) return resl;
        return merge(resl, resr);
    }
};

constexpr int MM = 1e5 + 5, LOG = 18;


// holy super cancer

vector<segment_tree> segs;
int parents[LOG][MM], ins[LOG][MM], outs[LOG][MM];
//vector<unordered_map<int, int>> parents, ins, outs;
vector<vector<int>> orders;
vector<vector<ll>> dists;
int n, q, subtree_size[MM], centroid_to_dep[MM], centroid_to_lvl[MM];
ll w;
int centroid_depth = 0;
bool is_removed[MM];
vector<pi> adj[MM];
vector<int> ancestors[MM];
array<ll, 3> edges[MM];
ll stored_distances[MM];
set<pi> max_distances;

// template taken from https://usaco.guide/plat/centroid?lang=cpp

int get_subtree_size(int node, int parent = -1) {
    subtree_size[node] = 1;
    for (auto &[child, _] : adj[node]) {
        if (child == parent || is_removed[child]) { continue; }
        subtree_size[node] += get_subtree_size(child, node);
    }
    return subtree_size[node];
}


int get_centroid(int node, int tree_size, int parent = -1) {
    for (auto &[child, _] : adj[node]) {
        if (child == parent || is_removed[child]) { continue; }
        if (subtree_size[child] * 2 > tree_size) {
            return get_centroid(child, tree_size, node);
        }
    }
    return node;
}

void calc_dist(int node, int centroid, int child_group, int lvl, int parent = -1, ll cur_dist = 1) {
    ins[lvl][node] = orders[centroid_depth].size();
    parents[lvl][node] = parent;
    orders[centroid_depth].push_back(child_group);
    dists[centroid_depth].push_back(cur_dist);
    for (auto &[child, dist] : adj[node]) {
        if (child == parent || is_removed[child]) { continue; }

        cur_dist += dist;

        calc_dist(child, centroid, child_group, lvl, node, cur_dist);

        cur_dist -= dist;
    }
    outs[lvl][node] = orders[centroid_depth].size();
    orders[centroid_depth].push_back(child_group);
    dists[centroid_depth].push_back(cur_dist);

    ancestors[node].push_back(centroid);
}

void fix_centroid(int centroid) {
    int depth = centroid_to_dep[centroid],
        lvl = centroid_to_lvl[centroid];
    if (stored_distances[centroid] > 0) {
        max_distances.erase({-stored_distances[centroid], centroid});
    }

    node first_max = segs[depth].query(0, orders[depth].size() - 1);

    ll new_dist = first_max.mx;
    if (first_max.orig != -1) {
        node second_max = merge(segs[depth].query(0, ins[lvl][first_max.orig] - 1),
                                segs[depth].query(outs[lvl][first_max.orig] + 1, orders[depth].size() - 1));
        new_dist += second_max.mx;
    }

    stored_distances[centroid] = new_dist;
    max_distances.insert({-new_dist, centroid});
}

void build_centroid_decomp(int node = 0, int lvl = 0) {
    int centroid = get_centroid(node, get_subtree_size(node));


    centroid_to_dep[centroid] = centroid_depth;
    centroid_to_lvl[centroid] = lvl;

    orders.emplace_back();
    dists.emplace_back();

    for (auto &[child, dist] : adj[centroid]) {
        if (is_removed[child]) { continue; }
        calc_dist(child, centroid, child, lvl, centroid, dist);
    }

    segs.emplace_back(orders[centroid_depth], dists[centroid_depth]);

    fix_centroid(centroid);

    is_removed[centroid] = true;

    for (auto &[child, _] : adj[centroid]) {
        if (is_removed[child]) { continue; }
        centroid_depth++;
        build_centroid_decomp(child, lvl + 1);
    }
}

int main() {
    cin.tie(0); cout.tie(0); ios::sync_with_stdio(0);
    cin >> n >> q >> w;
    for (int i = 0; i < n - 1; i++) {
        cin >> edges[i][0] >> edges[i][1] >> edges[i][2];
        --edges[i][0], --edges[i][1];
        adj[edges[i][0]].pb({edges[i][1], edges[i][2]});
        adj[edges[i][1]].pb({edges[i][0], edges[i][2]});
    }
    ll last = 0;

    memset(parents, -1, sizeof(parents));
    memset(ins, -1, sizeof(ins));
    memset(outs, -1, sizeof(outs));

    build_centroid_decomp();

    while (q--) {
        int v;
        ll weight; cin >> v >> weight;
        v = (v + last) % (n - 1);
        weight = (weight + last) % w;

        ll delta = weight - edges[v][2];
        set<int> has_updated;
        auto update_centroid = [&](int centroid) {
            if (has_updated.count(centroid)) {
                return;
            }
            has_updated.insert(centroid);
            int depth = centroid_to_dep[centroid], lvl = centroid_to_lvl[centroid], child = -1;
            if (/*parents[lvl].count(edges[v][0]) &&*/ parents[lvl][edges[v][0]] == edges[v][1]) {
                child = edges[v][0];
            }
            else if (/*parents[dep].count(edges[v][1]) && */parents[lvl][edges[v][1]] == edges[v][0]) {
                child = edges[v][1];
            }

            if (child != -1) {
                segs[depth].update(ins[lvl][child], outs[lvl][child], delta);

                fix_centroid(centroid);
            }
        };

        for (auto &centroid : ancestors[edges[v][0]]) {
            update_centroid(centroid);
        }

        for (auto &centroid : ancestors[edges[v][1]]) {
            update_centroid(centroid);
        }

        edges[v][2] = weight;

        last = -(*max_distances.begin())[0];

        cout << last << "\n";
    }
}

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