Submission #1277467

#	Time	Username	Problem	Language	Result	Execution time	Memory
1277467		not_amir	Dynamic Diameter (CEOI19_diameter)	C++20	31 / 100	5106 ms	408244 KiB

diameter

#include <bits/stdc++.h>
using namespace std;

#define int ll

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

vector<vector<int>> G;

vector<bool> in_c;
vector<int> siz;

void dfs(int v, int p) {
    siz[v] = 1;
    for (int u : G[v]) {
        if (in_c[u] || u == p)
            continue;
        dfs(u, v);
        siz[v] += siz[u];
    }
}

int get_cent(int v, int p, int N) {
    for (int u : G[v]) {
        if (in_c[u] || u == p)
            continue;
        if (siz[u] > N / 2)
            return get_cent(u, v, N);
    }
    return v;
}

multiset<ll, greater<>> CS;

void erase(ll w) {
    CS.erase(CS.find(w));
}

void insert(ll w) {
    CS.insert(w);
}

struct lvl {
    struct node {
        map<int, int> in, out;
        vector<ll> st, add;
        int n = 0;

        void update(int i, int l, int r, int tl, int tr, ll w) {
            if (l >= r)
                return;
            if (l == tl && r == tr)
                add[i] += w;
            else {
                int tm = (tl + tr) / 2;
                update(2 * i, l, min(tm, r), tl, tm, w),
                update(2 * i + 1, max(l, tm), r, tm, tr, w);
            }
            st[i] = add[i] + (tl + 1 == tr ? 0 : max(st[2 * i], st[2 * i + 1]));
        }

        void update_edge(int u, int v, ll w) {
            if (in[u] > in[v])
                swap(u, v);
            update(1, in[v], out[v], 0, n, w);
        }

        void dfs(int v, int p) {
            in[v] = n++;
            for (int u : G[v]) {
                if (in_c[u] || u == p)
                    continue;
                dfs(u, v);
            }
            out[v] = n;
        }

        void init(int v, int p) {
            dfs(v, p);
            int N = 1;
            while (N < n)
                N *= 2;
            st.resize(4 * N);
            add.resize(4 * N);
        }
    };

    multiset<ll, greater<>> S;

    ll calc() {
        if (S.empty())
            return 0;
        if (S.size() == 1)
            return *S.begin();
        return *S.begin() + *next(S.begin());
    }

    map<int, node*> nodes;
    int d;

    void init(int v, int _d) {
        d = _d;
        nodes[v] = nullptr;
        for (int u : G[v]) {
            if (in_c[u])
                continue;
            node *cur = new node();
            cur->init(u, v);
            for (auto [v, jnk] : cur->in)
                nodes[v] = cur;
            S.insert(0);
        }
        insert(calc());
    }

    void update_edge(int u, int v, ll w) {
        erase(calc());
        if (!nodes[v])
            swap(u, v);
        S.erase(S.find(nodes[v]->st[1]));
        if (nodes[u] && nodes[v])
            nodes[v]->update_edge(u, v, w);
        else
            nodes[v]->st[1] += w, nodes[v]->add[1] += w;
        S.insert(nodes[v]->st[1]);
        insert(calc());
    }
};

vector<lvl> dcmp;
vector<int> par;

void cent_decomposition(int v, int p, int d = 0) {
    dfs(v, -1);
    int c = get_cent(v, -1, siz[v]);
    par[c] = p;
    dcmp[c].init(c, d);
    in_c[c] = true;
    for (int u : G[c]) {
        if (in_c[u])
            continue;
        cent_decomposition(u, c, d + 1);
    }
}

vector<pair<pii, ll>> E;

void update_edge(int i, ll w) {
    auto [p, pw] = E[i];
    auto [u, v] = p;
    ll diff = w - pw;
    E[i].second = w;
    int c = dcmp[u].d < dcmp[v].d ? u : v;
    while (c) {
        dcmp[c].update_edge(u, v, diff);
        c = par[c];
    }
}

int32_t main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n, q, w;
    cin >> n >> q >> w;
    G.resize(n + 1);
    in_c.resize(n + 1);
    siz.resize(n + 1);
    dcmp.resize(n + 1);
    par.resize(n + 1);
    E.resize(n);
    vector<ll> qu(n);
    for (int i = 1; i < n; i++) {
        int a, b;
        ll c;
        cin >> a >> b >> c;
        E[i] = {{a, b}, 0};
        qu[i] = c;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    cent_decomposition(1, 0);
    for (int i = 1; i < n; i++) {
        update_edge(i, qu[i]);
    }
    ll last = 0;
    while (q--) {
        int d;
        ll e;
        cin >> d >> e;
        d = (last + d) % (n - 1);
        e = (last + e) % w;
        update_edge(d + 1, e);
        last = *CS.begin();
        cout << last << '\n';
    }
}

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