Submission #1213562

#	Time	Username	Problem	Language	Result	Execution time	Memory
1213562		lopkus	Dynamic Diameter (CEOI19_diameter)	C++20	100 / 100	143 ms	31720 KiB

diameter

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 100100;
int n;
int nds[N]; // map edges to node
ll a[N];
vector<int> adj[N];
vector<pair<pair<int, int>, ll>> adj2[N];
enum Type { Compress, Vertex, AddVertex, AddEdge, Rake };
struct StaticTopTree {
    int l[4 * N], r[4 * N], p[4 * N], root, idx;
    Type t[4 * N];
    int dfs(int v) {
        int sz = 1, big = 0;
        for (auto& x : adj[v]) {
            int s = dfs(x);
            sz += s;
            if (big < s) big = s, swap(x, adj[v][0]);
        }
        return sz;
    }
    int add(int v, int lc, int rc, Type type) {
        if (v == -1) v = ++idx;
        p[v] = -1, l[v] = lc, r[v] = rc, t[v] = type;
        if (lc != -1) p[lc] = v;
        if (rc != -1) p[rc] = v;
        return v;
    }
    pair<int, int> merge(vector<pair<int, int>>& path, Type type) {
        if ((int)path.size() == 1) return path[0];
        int sz = 0;
        for (auto& [_, s] : path) sz += s;
        vector<pair<int, int>> pl, pr;
        for (auto& [x, s] : path) {
            (s < sz ? pl : pr).push_back({ x, s }), sz -= 2 * s;
        }
        auto [i, si] = merge(pl, type);
        auto [j, sj] = merge(pr, type);
        return { add(-1, i, j, type), si + sj };
    }
    pair<int, int> rake(int i) {
        vector<pair<int, int>> path;
        for (int j = 1;j < (int)adj[i].size();j++) {
            path.push_back(add_edge(adj[i][j]));
        }
        return path.empty() ? make_pair(-1, 0) : merge(path, Type::Rake);
    }
    pair<int, int> compress(int i) {
        vector<pair<int, int>> path{ add_vertex(i) };
        while (!adj[i].empty()) path.push_back(add_vertex(i = adj[i][0]));
        return merge(path, Type::Compress);
    }
    pair<int, int> add_vertex(int i) {
        auto [j, s] = rake(i);
        return { add(i, j, -1, j == -1 ? Type::Vertex : Type::AddVertex), s + 1 };
    }
    pair<int, int> add_edge(int i) {
        auto [j, s] = compress(i);
        return { add(-1, j, -1, Type::AddEdge), s };
    }
    void build() {
        idx = n;
        dfs(1);
        root = compress(1).first;
    }
} stt;
void dfsd(int v, int p = -1) {
    for (auto& x : adj2[v]) {
        if (x.first.second == p) continue;
        nds[x.first.first] = x.first.second;
        a[x.first.second] = x.second;
        adj[v].push_back(x.first.second);
        dfsd(x.first.second, v);
    }
}
struct Point {
    ll mx, mx1, mx2;
} point[4 * N];
struct Path {
    ll mx, l, pref, mxp;
} path[4 * N];
Path vertex(int i) {
    return { 0ll, a[i], a[i], a[i] };
}
Path add_vertex(Point d, int i) {
    return { max(d.mx, d.mx1 + d.mx2), a[i], a[i] + d.mx1, d.mx1 };
}
Path compress(Path p, Path c) {
    return{ max({p.mx, c.mx, p.mxp + c.pref}), p.l + c.l, max(c.pref + p.l, p.pref), max(c.mxp, p.mxp + c.l) };
}
Point add_edge(Path d) {
    return { d.mx, d.pref, 0ll };
}
Point rake(Point l, Point r) {
    Point res = { max(l.mx, r.mx), l.mx1, l.mx2 };
    res.mx2 = max(res.mx2, r.mx1);
    if (res.mx1 < res.mx2) swap(res.mx1, res.mx2);
    res.mx2 = max(res.mx2, r.mx2);
    if (res.mx1 < res.mx2) swap(res.mx1, res.mx2);
    return res;
}
void update(int v) {
    if (stt.t[v] == Type::Vertex) path[v] = vertex(v);
    else if (stt.t[v] == Type::AddVertex) path[v] = add_vertex(point[stt.l[v]], v);
    else if (stt.t[v] == Type::Compress) path[v] = compress(path[stt.l[v]], path[stt.r[v]]);
    else if (stt.t[v] == Type::AddEdge) point[v] = add_edge(path[stt.l[v]]);
    else point[v] = rake(point[stt.l[v]], point[stt.r[v]]);
}
void dfs(int v) {
    if (stt.l[v] != -1) dfs(stt.l[v]);
    if (stt.r[v] != -1) dfs(stt.r[v]);
    update(v);
}
int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int q;
    ll mw;
    cin >> n >> q >> mw;
    for (int i = 0;i < n - 1;i++) {
        int u, v;
        ll w;
        cin >> u >> v >> w;
        adj2[u].push_back({ {i, v}, w });
        adj2[v].push_back({ {i, u}, w });
    }
    dfsd(1);
    stt.build();
    dfs(stt.root);
    ll last = 0;
    while (q--) {
        int e;
        ll w;
        cin >> e >> w;
        e = (e + last) % (n - 1);
        int v = nds[e];
        a[v] = (w + last) % mw;
        while (v != -1) update(v), v = stt.p[v];
        cout << (last = path[stt.root].mx) << '\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