Submission #430338

#	Time	Username	Problem	Language	Result	Execution time	Memory
430338		jhwest2	Dynamic Diameter (CEOI19_diameter)	C++14	31 / 100	5112 ms	422992 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, lint> pint;
const int M = 1 << 17, N = 20;

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

pint operator+(const pint &a, const pint &b) {
    if (a.va > b.va) return pint(a.va, max(a.vb, b.va));
    return pint(b.va, max(a.va, b.vb));
}
struct SEG {
    pint T[M << 2]; lint L[M << 2];

    void push(int lo, int hi, int idx) {
        if (!L[idx]) return;
        T[idx].va += L[idx]; 
        if (lo != hi) {
            T[idx].vb += L[idx];
            L[idx << 1] += L[idx];
            L[idx << 1 | 1] += L[idx];
        }
        L[idx] = 0;
    }
    pint 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] = update(a, b, x, lo, lo + hi >> 1, idx << 1) +
            update(a, b, x, 1 + (lo + hi >> 1), hi, idx << 1 | 1);
    }
    pint query(int a, int b, int lo = 1, int hi = n, int idx = 1) {
        push(lo, hi, idx);
        if (b < lo || a > hi) return pint(0, 0);
        if (a <= lo && hi <= b) return T[idx];
        return query(a, b, lo, lo + hi >> 1, idx << 1) +
            query(a, b, 1 + (lo + hi >> 1), hi, idx << 1 | 1);
    }
} S[N], T[N], Ans;

int Sub[M], Chk[M], in, kn;
int At[N][M], Col[N][M], Dep[N][M], L[N][M], R[N][M], B[N][M], Lo[M], Hi[M];
lint A[N][M];

vector<pint> G[M];

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 = kn = 0; p = d;
        }
        dfs(k, k); k = cent(k, k, Sub[k]);
        L[d][k] = ++in; Col[d][k] = k; At[d][k] = k; Lo[k] = kn + 1;
        for (auto [w, x] : G[k]) if (!Chk[x]) {
            B[d][x] = ++kn;
            dfs2(k, x, d, k, x, w);
            Q.emplace(d + 1, x);
            A[d][x] = S[d].query(L[d][x], R[d][x]).va;
            T[d].update(kn, kn, A[d][x]);
        }
        R[d][k] = in; Chk[k] = 1; Hi[k] = kn;
        pint v = T[d].query(Lo[k], Hi[k]);
        Ans.update(k, k, v.va + v.vb);
    }
}
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], j = B[i][x];
        A[i][x] = S[i].query(L[i][x], R[i][x]).va;
        T[i].update(j, j, A[i][x] - T[i].query(j, j).va);

        pint v = T[i].query(Lo[r], Hi[r]);
        Ans.update(r, r, v.va + v.vb - Ans.query(r, r).va);
    }
}
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;
        last = Ans.query(1, n).va; cout << last << '\n';
    }
}

Compilation message (stderr)

diameter.cpp: In member function 'pint SEG::update(int, int, lint, int, int, int)':
diameter.cpp:37:48: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   37 |         return T[idx] = update(a, b, x, lo, lo + hi >> 1, idx << 1) +
      |                                             ~~~^~~~
diameter.cpp:38:37: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   38 |             update(a, b, x, 1 + (lo + hi >> 1), hi, idx << 1 | 1);
      |                                  ~~~^~~~
diameter.cpp: In member function 'pint SEG::query(int, int, int, int, int)':
diameter.cpp:44:35: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   44 |         return query(a, b, lo, lo + hi >> 1, idx << 1) +
      |                                ~~~^~~~
diameter.cpp:45:33: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   45 |             query(a, b, 1 + (lo + hi >> 1), hi, idx << 1 | 1);
      |                              ~~~^~~~
diameter.cpp: In function 'void dfs(int, int)':
diameter.cpp:57:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   57 |     for (auto [d, x] : G[cur]) if (p != x && !Chk[x]) {
      |               ^
diameter.cpp: In function 'int cent(int, int, int)':
diameter.cpp:62:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   62 |     for (auto [d, x] : G[cur]) if (p != x && !Chk[x]) {
      |               ^
diameter.cpp: In function 'void dfs2(int, int, int, int, int, lint)':
diameter.cpp:70:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   70 |     for (auto [w, x] : G[cur]) if (p != x && !Chk[x]) {
      |               ^
diameter.cpp: In function 'void init()':
diameter.cpp:80:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   80 |         auto [d, k] = Q.front(); Q.pop();
      |              ^
diameter.cpp:86:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   86 |         for (auto [w, x] : G[k]) if (!Chk[x]) {
      |                   ^

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