Submission #1277526

#	Time	Username	Problem	Language	Result	Execution time	Memory
1277526		not_amir	Dynamic Diameter (CEOI19_diameter)	C++20	49 / 100	1386 ms	181436 KiB

diameter

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

#pragma GCC optimize("O3, 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] * 2 > N)
            return get_cent(u, v, N);
    }
    return v;
}

struct del_pq {
    priority_queue<ll> pq_add, pq_del;

    void push(ll x) {
        pq_add.push(x);
    }

    void pop(ll x) {
        pq_del.push(x);
    }

    ll top() {
        while (!pq_del.empty() && pq_add.top() == pq_del.top())
            pq_add.pop(), pq_del.pop();
        return pq_add.empty() ? 0 : pq_add.top();
    }
};

del_pq CS;

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

void insert(ll w) {
    CS.push(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, st[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] + 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;
    del_pq S;

    ll calc() {
        ll f = S.top();
        S.pop(f);
        ll ret = f + S.top();
        S.push(f);
        return ret;
    }

    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.push(0);
        }
        insert(0);
    }

    void update_edge(int u, int v, ll w) {
        erase(calc());
        if (!nodes[v][d])
            swap(u, v);
        S.pop(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.push(nodes[v][d]->st[1]);
        insert(calc());
    }
};

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

int _n;

void cent_decomposition(int v, int p, int d = 0) {
    dfs(v, -1);
    if (p == 0)
        assert(siz[v] == _n);
    int c = get_cent(v, -1, siz[v]);
    par[c] = p;
    in_c[c] = true;
    dcmp[c].init(c, d);
    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;
    bool move_a = false, move_b = false;
    while (lu != lv) {
        if (dcmp[lu].d > dcmp[lv].d)
            lu = par[lu], move_a = true;
        else
            lv = par[lv], move_b = true;
    }
    if(!(move_a ^ move_b))
        exit(5);
    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;
    _n = n;
    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++)
        if (!in_c[i])
            exit(5);
    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.top();
        cout << last << '\n';
    }
}

Compilation message (stderr)

diameter.cpp:4:40: warning: bad option '-f unroll-loops' to pragma 'optimize' [-Wpragmas]
    4 | #pragma GCC optimize("O3, unroll-loops")
      |                                        ^
diameter.cpp:14:22: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
   14 | void dfs(int v, int p) {
      |                      ^
diameter.cpp:24:33: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
   24 | int get_cent(int v, int p, int N) {
      |                                 ^
diameter.cpp:37:19: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
   37 |     void push(ll x) {
      |                   ^
diameter.cpp:41:18: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
   41 |     void pop(ll x) {
      |                  ^
diameter.cpp:45:12: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
   45 |     ll top() {
      |            ^
diameter.cpp:54:16: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
   54 | void erase(ll w) {
      |                ^
diameter.cpp:58:17: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
   58 | void insert(ll w) {
      |                 ^
diameter.cpp:69:58: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
   69 |     void update(int i, int l, int r, int tl, int tr, ll w) {
      |                                                          ^
diameter.cpp:82:40: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
   82 |     void update_edge(int u, int v, ll w) {
      |                                        ^
diameter.cpp:88:26: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
   88 |     void dfs(int v, int p) {
      |                          ^
diameter.cpp:99:35: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
   99 |     void init(int v, int p, int _d) {
      |                                   ^
diameter.cpp:116:13: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
  116 |     ll calc() {
      |             ^
diameter.cpp:124:28: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
  124 |     void init(int v, int _d) {
      |                            ^
diameter.cpp:139:40: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
  139 |     void update_edge(int u, int v, ll w) {
      |                                        ^
diameter.cpp:158:48: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
  158 | void cent_decomposition(int v, int p, int d = 0) {
      |                                                ^
diameter.cpp:175:29: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
  175 | void update_edge(int i, ll w) {
      |                             ^
diameter.cpp:197:14: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
  197 | int32_t main() {
      |              ^

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