Submission #430425

#	Time	Username	Problem	Language	Result	Execution time	Memory
430425		jhwest2	Dynamic Diameter (CEOI19_diameter)	C++17	49 / 100	5069 ms	176512 KiB

diameter

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#define va first
#define vb second
using namespace std;
typedef long long lint;
typedef pair<lint, int> pint;
const int M = 1 << 17, N = 20;

lint n, q, w, X[M], Y[M], W[M];

struct SEG {
    lint T[M << 2], L[M << 2];

    void push(int lo, int hi, int idx) {
        if (!L[idx]) return; T[idx] += L[idx];
        if (lo != hi) {
            L[idx << 1] += L[idx];
            L[idx << 1 | 1] += L[idx];
        }
        L[idx] = 0;
    }
    lint update(int a, int b, lint x, int lo = 1, int hi = n, int idx = 1) {
        push(lo, hi, idx);
        if (b < lo || a > hi) return T[idx];
        if (a <= lo && hi <= b) {
            L[idx] += x; push(lo, hi, idx); return T[idx];
        }
        return T[idx] = max(update(a, b, x, lo, lo + hi >> 1, idx << 1),
            update(a, b, x, 1 + (lo + hi >> 1), hi, idx << 1 | 1));
    }
    lint query(int a, int b, int lo = 1, int hi = n, int idx = 1) {
        push(lo, hi, idx);
        if (b < lo || a > hi) return 0;
        if (a <= lo && hi <= b) return T[idx];
        return max(query(a, b, lo, lo + hi >> 1, idx << 1),
            query(a, b, 1 + (lo + hi >> 1), hi, idx << 1 | 1));
    }
} S[N];

int Sub[M], Chk[M], in = 0;
int At[N][M], Col[N][M], Dep[N][M], L[N][M], R[N][M];
lint A[N][M], Val[M];

vector<pint> G[M];
multiset<lint, greater<lint>> St[M];
priority_queue<pint> Ans;

void dfs(int p, int cur) {
    Sub[cur] = 1;
    for (auto [d, x] : G[cur]) if (p != x && !Chk[x]) {
        dfs(cur, x); Sub[cur] += Sub[x];
    }
}
int cent(int p, int cur, int s) {
    for (auto [d, x] : G[cur]) if (p != x && !Chk[x]) {
        if (Sub[x] > s / 2) return cent(cur, x, s);
    }
    return cur;
}
void dfs2(int p, int cur, int d, int r, int k, lint dist) {
    At[d][cur] = r; L[d][cur] = ++in; Col[d][cur] = k;
    S[d].update(in, in, dist);
    for (auto [w, x] : G[cur]) if (p != x && !Chk[x]) {
        Dep[d][x] = Dep[d][cur] + 1;
        dfs2(cur, x, d, r, k, dist + w);
    }
    R[d][cur] = in;
}
void init() {
    queue<pint> Q; Q.emplace(0, 1);
    int p = 0;
    while (!Q.empty()) {
        auto [d, k] = Q.front(); Q.pop();
        if (p != d) {
            in = 0; p = d;
        }
        dfs(k, k); k = cent(k, k, Sub[k]);
        L[d][k] = ++in; Col[d][k] = k; At[d][k] = k;
        for (auto [w, x] : G[k]) if (!Chk[x]) {
            dfs2(k, x, d, k, x, w);
            Q.emplace(d + 1, x);
            A[d][x] = S[d].query(L[d][x], R[d][x]);
            St[k].insert(A[d][x]);
        }
        R[d][k] = in; Chk[k] = 1;
        St[k].insert(0);
        Val[k] = *St[k].begin() + *next(St[k].begin());
        Ans.emplace(Val[k], k);
    }
}
void update(int u, int v, lint w) {
    for (int i = 0; i < N; i++) {
        if (At[i][u] != At[i][v]) break;
        if (L[i][u] > L[i][v]) swap(u, v);
        S[i].update(L[i][v], R[i][v], w);

        int x = Col[i][v], r = At[i][v];
        St[r].erase(St[r].find(A[i][x]));
        A[i][x] = S[i].query(L[i][x], R[i][x]);
        St[r].insert(A[i][x]);

        Val[r] = *St[r].begin() + *next(St[r].begin());
        Ans.emplace(Val[r], r);
    }
}
int main() {
    cin.tie(0); ios_base::sync_with_stdio(0);
    cin >> n >> q >> w;
    for (int i = 0; i + 1 < n; i++) {
        cin >> X[i] >> Y[i] >> W[i];
        G[X[i]].emplace_back(W[i], Y[i]);
        G[Y[i]].emplace_back(W[i], X[i]);
    }
    init();
    lint last = 0;
    for (int i = 0; i < q; i++) {
        lint k, x; cin >> k >> x;
        k = (k + last) % (n - 1); x = (x + last) % w;
        int u = X[k], v = Y[k];
        update(u, v, x - W[k]); W[k] = x;
        while (!Ans.empty() && Ans.top().va != Val[Ans.top().vb]) {
            Ans.pop();
        }
        last = Ans.top().va; cout << last << '\n';
    }
}

Compilation message (stderr)

diameter.cpp: In member function 'void SEG::push(int, int, int)':
diameter.cpp:18:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   18 |         if (!L[idx]) return; T[idx] += L[idx];
      |         ^~
diameter.cpp:18:30: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   18 |         if (!L[idx]) return; T[idx] += L[idx];
      |                              ^
diameter.cpp: In member function 'lint SEG::update(int, int, lint, int, int, int)':
diameter.cpp:31:52: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   31 |         return T[idx] = max(update(a, b, x, lo, lo + hi >> 1, idx << 1),
      |                                                 ~~~^~~~
diameter.cpp:32:37: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   32 |             update(a, b, x, 1 + (lo + hi >> 1), hi, idx << 1 | 1));
      |                                  ~~~^~~~
diameter.cpp: In member function 'lint SEG::query(int, int, int, int, int)':
diameter.cpp:38:39: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   38 |         return max(query(a, b, lo, lo + hi >> 1, idx << 1),
      |                                    ~~~^~~~
diameter.cpp:39:33: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   39 |             query(a, b, 1 + (lo + hi >> 1), hi, idx << 1 | 1));
      |                              ~~~^~~~

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