제출 #1277492

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1277492		not_amir	Dynamic Diameter (CEOI19_diameter)	C++20	49 / 100	5093 ms	127964 KiB

diameter

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

#pragma GCC optimize("unroll-loops")

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

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);
}

vector<vector<int>> in, out;

struct node {
    vector<ll> st, add;
    vector<int> V;
    int n = 0, N, d;

    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][d] > in[v][d])
            swap(u, v);
        update(1, in[v][d], out[v][d], 0, N, w);
    }

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

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

vector<vector<node*>> nodes;

struct lvl {
    int d;
    multiset<ll, greater<>> S;


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

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

    void update_edge(int u, int v, ll w) {
        erase(calc());
        if (!nodes[v][d])
            swap(u, v);
        S.erase(S.find(nodes[v][d]->st[1]));
        if (nodes[u][d] && nodes[v][d])
            nodes[v][d]->update_edge(u, v, w);
        else
            nodes[v][d]->st[1] += w, nodes[v][d]->add[1] += w;
        S.insert(nodes[v][d]->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 lu = u, lv = v;
    while (lu != lv) {
        if (dcmp[lu].d > dcmp[lv].d)
            lu = par[lu];
        else
            lv = par[lv];
    }
    assert(lu == lv);
    int c = lv;
    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);
    in.resize(n + 1);
    out.resize(n + 1);
    nodes.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: 18 / 18
• Subtask 5: 0 / 24
• Subtask 6: 0 / 27