제출 #1305935

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1305935		maxcruickshanks	Dynamic Diameter (CEOI19_diameter)	C++20	100 / 100	3626 ms	309908 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;
};
inline node merge(const node &l, const 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.resize(2 * S);
        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]);
        }
    }

    inline 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[MM][LOG], ins[MM][LOG], outs[MM][LOG];

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;
multiset<ll> max_distanc;

// 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[node][lvl] = orders[centroid_depth].size();
    parents[node][lvl] = 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[node][lvl] = 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_distanc.erase(max_distanc.find(-stored_distances[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[first_max.orig][lvl] - 1),
                                segs[depth].query(outs[first_max.orig][lvl] + 1, orders[depth].size() - 1));
        new_dist += second_max.mx;
    }

    stored_distances[centroid] = new_dist;
    max_distanc.insert(-new_dist);
}

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();
    orders[centroid_depth].reserve(2 * (get_subtree_size(node) + 2));
    dists[centroid_depth].reserve(2 * (get_subtree_size(node) + 2));

    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[edges[v][0]][lvl] == edges[v][1]) {
                child = edges[v][0];
            }
            else if (/*parents[dep].count(edges[v][1]) && */parents[edges[v][1]][lvl] == edges[v][0]) {
                child = edges[v][1];
            }

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

                fix_centroid(centroid);
            }
        };

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

        int deep = (ancestors[edges[v][0]].size() > ancestors[edges[v][1]].size()) ? edges[v][0] : edges[v][1];

        for (auto &centroid : ancestors[deep]) {
            update_centroid(centroid);
        }

        edges[v][2] = weight;

        last = -(*max_distanc.begin());

        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