Submission #658926

#	Time	Username	Problem	Language	Result	Execution time	Memory
658926		dooompy	Dynamic Diameter (CEOI19_diameter)	C++17	100 / 100	3488 ms	250772 KiB

diameter

#include "bits/stdc++.h"

using namespace std;

void abc() {cout << endl;}
template <typename T, typename ...U> void abc(T a, U ...b) {
    cout << a << ' ', abc(b...);
}
template <typename T> void printv(T l, T r) {
    while (l != r) cout << *l << " \n"[++l == r];
}
template <typename A, typename B> istream& operator >> (istream& o, pair<A, B> &a) {
    return o >> a.first >> a.second;
}
template <typename A, typename B> ostream& operator << (ostream& o, pair<A, B> a) {
    return o << '(' << a.first << ", " << a.second << ')';
}
template <typename T> ostream& operator << (ostream& o, vector<T> a) {
    bool is = false;
    for (T i : a) {o << (is ? ' ' : '{'), is = true, o << i;}
    return o << '}';
}

#ifdef local
#define test(args...) abc("[" + string(#args) + "]", args)
#else
#define test(args...) void(0)
#endif

using ll = long long;

#define int ll

struct node {
    int val, lazy;
};

struct update {
    int x, l, r, ql, qr, id, cent, edgeid;
};

struct edge {
    int to; ll cost; int id;
};

vector<update> history[100005];
vector<edge> adj[100005];
int sz[100005];
bool seen[100005];
int timer = 1;
int st[100005], en[100005];
multiset<ll> pathd[100005], total;
int ct = 0;

vector<vector<node>> tree;

ll get() {
    return *prev(total.end());
}

ll calc(multiset<ll> &cur) {
    if (cur.empty()) return 0;
    if (cur.size() == 1) return *cur.begin();

    auto itr = cur.end(); itr--;
    ll sum = *itr; itr--;
    sum += *itr;

    return sum;
}

void predfs(int node, int par = -1) {
    ct++;
    sz[node] = 1;
    for (auto nxt : adj[node]) {
        if (nxt.to == par)continue;
        if (seen[nxt.to]) continue;
        predfs(nxt.to, node);
        sz[node] += sz[nxt.to];
    }
}

int find(int node, int root, int par = -1) {

    for (auto nxt : adj[node]) {
        if (seen[nxt.to]) continue;
        if (nxt.to == par)continue;
        if (sz[nxt.to] > ct / 2) return find(nxt.to, root, node);
    }

    return node;
}

void dfs(int node, int par = -1) {
    st[node] = timer++;

    for (auto nxt : adj[node]) {
        if (seen[nxt.to] || nxt.to == par) continue;
        dfs(nxt.to, node);
    }

    en[node] = timer - 1;
}

void pushdown(int x, int l, int r, int id) {
    if (l == r) return;

    tree[id][2 * x].val += tree[id][x].lazy;
    tree[id][2 * x].lazy += tree[id][x].lazy;
    tree[id][2 * x + 1].val += tree[id][x].lazy;
    tree[id][2 * x + 1].lazy += tree[id][x].lazy;

    tree[id][x].lazy = 0;
}

void update(int x, int l, int r, int ql, int qr, int id, int cent, int v) {
    if (ql <= l && r <= qr) {
        if (x == 1) {
            pathd[cent].erase(pathd[cent].find(tree[id][x].val));
        }

        tree[id][x].val += v;
        tree[id][x].lazy += v;

        if (x == 1) {
            pathd[cent].insert(tree[id][x].val);
        }
        return;
    }

    if (l > qr || ql > r) return;

    pushdown(x, l, r, id);
    int mid = (l + r) / 2;

    update(2 * x, l, mid, ql, qr, id, cent, v);
    update(2 * x + 1, mid + 1, r, ql, qr, id, cent, v);

    if (x == 1) {
        pathd[cent].erase(pathd[cent].find(tree[id][x].val));
    }

    tree[id][x].val = max(tree[id][2 * x].val, tree[id][2 * x + 1].val);

    if (x == 1) {
        pathd[cent].insert(tree[id][x].val);
    }
}

void updateall(int node, int par, int cent) {
    for (auto nxt : adj[node]) {
        if (seen[nxt.to] || par == nxt.to) continue;

        update(1, 1, timer, st[nxt.to], en[nxt.to], tree.size() - 1, cent, nxt.cost);
        history[nxt.id].push_back({1, 1, timer, st[nxt.to], en[nxt.to], (int) tree.size() - 1, cent, nxt.id});

        updateall(nxt.to, node, cent);
    }
}

void centroid(int node) {
    ct = 0;
    predfs(node);

    if (ct == 1) {
        seen[node] = true; return;
    }
    int cent = find(node, node);

    for (auto nxt : adj[cent]) {
        if (seen[nxt.to]) continue;

        timer = 1;

        dfs(nxt.to, cent);

        tree.push_back({});
        tree.back().resize(4 * (timer + 1));
        pathd[cent].insert(0);

        update(1, 1, timer, st[nxt.to], en[nxt.to], tree.size() - 1, cent, nxt.cost);
        history[nxt.id].push_back({1, 1, timer, st[nxt.to], en[nxt.to], (int) tree.size() - 1, cent, nxt.id});

        updateall(nxt.to, cent, cent);
    }

    total.insert(calc(pathd[cent]));

    seen[cent] = true;

    for (auto nxt : adj[cent]) {
        if (seen[nxt.to]) continue;
        centroid(nxt.to);
    }
}

ll edgeinfo[100005];

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
//    freopen("", "r", stdin);
//    freopen("", "w", stdout);
    int n, q, w; cin >> n >> q >> w;

    for (int i = 1; i <= n-1; i++) {
        int a, b; cin >> a >> b;
        ll c; cin >> c;
        adj[a].push_back({b, c, i});
        adj[b].push_back({a, c, i});
        edgeinfo[i] = c;
    }

    centroid(1);

//    cout << *prev(total.end()) << endl;

    ll last = 0;

    for (int i = 0; i < q; i++) {
        ll d, e; cin >> d >> e;
        d = (d + last) % (n - 1);
        d++;
        e = (e + last) % w;

        ll delta = e - edgeinfo[d];
        edgeinfo[d] = e;

        for (auto [x, l, r, ql, qr, id, cent, edgeid] : history[d]) {
            total.erase(total.find(calc(pathd[cent])));
            update(x, l, r, ql, qr, id, cent, delta);
            total.insert(calc(pathd[cent]));
        }

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