Submission #572763

#	Time	Username	Problem	Language	Result	Execution time	Memory
572763		piOOE	Dynamic Diameter (CEOI19_diameter)	C++17	100 / 100	3934 ms	327476 KiB

diameter

#include <bits/stdc++.h>

using namespace std;

#define sz(x) ((int)size(x))
#define all(x) begin(x), end(x)
#define trace(x) cout << #x << ": " << (x) << endl;

typedef long long ll;

mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

int rand(int l, int r) { return (int) ((ll) rnd() % (r - l + 1)) + l; }

struct segtree {
    int sz = 1;
    vector<ll> mx, add;

    segtree() = default;

    segtree(int n) {
        sz = 1;
        while (sz < n) {
            sz <<= 1;
        }
        mx.assign(sz << 1, 0), add.assign(sz << 1, 0);
    }

    void init(int n) {
        sz = 1;
        while (sz < n) {
            sz <<= 1;
        }
        mx.assign(sz << 1, 0), add.assign(sz << 1, 0);
    }

    void modify(int l, int r, ll val, int x, int lx, int rx) {
        if (l >= rx || lx >= r) {
            return;
        }
        if (l <= lx && rx <= r) {
            mx[x] += val;
            add[x] += val;
            return;
        }
        int m = (lx + rx) >> 1;
        modify(l, r, val, x << 1, lx, m), modify(l, r, val, x << 1 | 1, m, rx);
        mx[x] = max(mx[x << 1], mx[x << 1 | 1]) + add[x];
    }

    void modify(int l, int r, ll val) {
        modify(l, r, val, 1, 0, sz);
    }

    ll get(int l, int r, int x, int lx, int rx) {
        if (l >= rx || lx >= r) {
            return 0;
        }
        if (l <= lx && rx <= r) {
            return mx[x];
        }
        int m = (lx + rx) >> 1;
        return max(get(l, r, x << 1, lx, m), get(l, r, x << 1 | 1, m, rx)) + add[x];
    }

    ll get(int l, int r) {
        return get(l, r, 1, 0, sz);
    }

};

const int N = 100000, logn = 18;

int A[N], B[N], Root[logn][N], Parent[logn][N], Child[logn][N], siz[N], lst[N], tin[logn][N], tout[logn][N], PP[logn][N], sz[N], T = 0;
segtree st[logn][N];
multiset<ll, greater<>> mult[logn][N];
ll W[N], diam[logn][N];

bool used[N];

vector<pair<int, int>> g[N];

int centroid(int v, int n, int p) {
    for (auto [to, i]: g[v]) {
        if (!used[to] && to != p && sz[to] * 2 > n) {
            return centroid(to, n, v);
        }
    }
    return v;
}

void calc_sz(int v, int p) {
    sz[v] = 1;
    for (auto [to, i]: g[v]) {
        if (!used[to] && to != p) {
            calc_sz(to, v);
            sz[v] += sz[to];
        }
    }
}

void dfs(int v, int p, int id, int root, int pp) {
    Root[siz[v]][id] = root;
    Parent[siz[v]][id] = p;
    Child[siz[v]][id] = v;
    PP[siz[v]][id] = pp;
    tin[siz[v]][v] = T++;
    for (auto [to, j]: g[v]) {
        if (!used[to] && to != p) {
            dfs(to, v, j, root, pp);
        }
    }
    tout[siz[v]][v] = T;
    st[siz[v]][root].modify(tin[siz[v]][v], tout[siz[v]][v], W[id]);
    ++siz[v];
}

multiset<ll, greater<>> bestDiam;

void solve(int v) {
    used[v] = true;
    calc_sz(v, -1);
    T = 0;
    st[siz[v]][v].init(sz[v]);
    for (auto [to, i]: g[v]) {
        if (!used[to]) {
            dfs(to, v, i, v, to);
            mult[siz[v]][v].insert(st[siz[v]][v].get(tin[siz[v]][to], tout[siz[v]][to]));
        }
    }
    if (!mult[siz[v]][v].empty()) {
        if (sz(mult[siz[v]][v]) == 1) {
            diam[siz[v]][v] = *mult[siz[v]][v].begin();
        } else {
            diam[siz[v]][v] = (*mult[siz[v]][v].begin()) + (*next(mult[siz[v]][v].begin()));
        }
    }
    bestDiam.insert(diam[siz[v]][v]);
    ++siz[v];
    for (auto [to, i] : g[v]) {
        if (!used[to]) {
            lst[i] = siz[v];
            solve(centroid(to, sz[to], -1));
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q;
    ll WW;
    cin >> n >> q >> WW;
    ll last = 0;
    for (int i = 0; i < n - 1; ++i) {
        cin >> A[i] >> B[i] >> W[i];
        --A[i], --B[i];
        g[A[i]].emplace_back(B[i], i);
        g[B[i]].emplace_back(A[i], i);
    }
    calc_sz(0, -1);
    solve(centroid(0, n, -1));
    assert(!bestDiam.empty());
    while (q--) {
        int i;
        ll w;
        cin >> i >> w;
        i = (last + i) % (n - 1);
        w = (w + last) % WW;
        ll zz = w;
        w = w - W[i];
        W[i] = zz;
        for (int j = 0; j < lst[i]; ++j) {
            int root = Root[j][i];
            int v = Child[j][i];
            int p = Parent[j][i];
            int pp = PP[j][i];
            bestDiam.extract(diam[j][root]);
            mult[j][root].extract(st[j][root].get(tin[j][pp], tout[j][pp]));
            st[j][root].modify(tin[j][v], tout[j][v], w);
            mult[j][root].insert(st[j][root].get(tin[j][pp], tout[j][pp]));
            if (!mult[j][root].empty()) {
                if (mult[j][root].size() == 1) {
                    diam[j][root] = *mult[j][root].begin();
                } else {
                    diam[j][root] = (*mult[j][root].begin()) + (*next(mult[j][root].begin()));
                }
            }
            bestDiam.insert(diam[j][root]);
        }
        assert(!bestDiam.empty());
        last = *bestDiam.begin();
        cout << last << '\n';
    }
    return 0;
}

Compilation message (stderr)

diameter.cpp: In function 'int main()':
diameter.cpp:176:17: warning: unused variable 'p' [-Wunused-variable]
  176 |             int p = Parent[j][i];
      |                 ^

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