Submission #841727

#	Time	Username	Problem	Language	Result	Execution time	Memory
841727		hoanghq2004	Dynamic Diameter (CEOI19_diameter)	C++17	100 / 100	247 ms	51680 KiB

diameter

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;

int n, q;
vector <pair <int, long long>> g[N];
int a[N], in[N], out[N], ti, euler[N * 3];
long long d[N];

void dfs(int u, int p) {
    in[u] = ++ti;
    euler[ti] = u;
    for (auto [v, w]: g[u]) {
        if (v == p) continue;
        d[v] = d[u] + w;
        dfs(v, u);
        euler[++ti] = u;
    }
    out[u] = ti;
}

struct node {
    long long mx, mn;
    long long uw, wv;
    long long uwv;
    long long lazy;
    node operator + (const node& other) const {
        node ret;
        ret.mn = min(mn, other.mn);
        ret.mx = max(mx, other.mx);
        ret.uw = max({uw, other.uw, mx - 2 * other.mn});
        ret.wv = max({wv, other.wv, other.mx - 2 * mn});
        ret.uwv = max({uwv, other.uwv, uw + other.mx, other.wv + mx});
        ret.lazy = 0;
        return ret;
    }
} st[N * 12];

void push(int id, long long delta) {
    st[id].mx += delta;
    st[id].mn += delta;
    st[id].uw -= delta;
    st[id].wv -= delta;
    st[id].lazy += delta;
}

void build(int id, int L, int R) {
    if (L == R) {
        st[id].mx = st[id].mn = d[euler[L]];
        st[id].uw = st[id].wv = - d[euler[L]];
        st[id].uwv = st[id].lazy = 0;
        return;
    }
    int mid = L + R >> 1;
    build(id * 2, L, mid);
    build(id * 2 + 1, mid + 1, R);
    st[id] = st[id * 2] + st[id * 2 + 1];
}

void add(int id, int L, int R, int u, int v, long long delta) {
    if (u > R || L > v) return;
    if (u <= L && R <= v) {
        push(id, delta);
        return;
    }
    if (st[id].lazy) {
        push(id * 2, st[id].lazy);
        push(id * 2 + 1, st[id].lazy);
        st[id].lazy = 0;
    }
    int mid = L + R >> 1;
    add(id * 2, L, mid, u, v, delta);
    add(id * 2 + 1, mid + 1, R, u, v, delta);
    st[id] = st[id * 2] + st[id * 2 + 1];
}

long long lambda, last;

int main() {
    ios :: sync_with_stdio(0); cin.tie(0);
    cin >> n >> q >> lambda;
    vector <tuple <int, int, long long>> edges;
    for (int i = 1; i < n; ++i) {
        int u, v;
        long long w;
        cin >> u >> v >> w;
        g[u].push_back({v, w});
        g[v].push_back({u, w});
        edges.push_back({u, v, w});
    }
    dfs(1, 0);
    build(1, 1, ti);
    while (q--) {
        int i;
        long long w;
        cin >> i >> w;
        i = (last + i) % (n - 1);
        w = (last + w) % lambda;
        auto &[u, v, _w] = edges[i];
        if (in[u] > in[v]) swap(u, v);
        add(1, 1, ti, in[v], out[v], w - _w);
        _w = w;
        last = st[1].uwv;
        cout << last << '\n';
    }
}

Compilation message (stderr)

diameter.cpp: In function 'void build(int, int, int)':
diameter.cpp:56:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   56 |     int mid = L + R >> 1;
      |               ~~^~~
diameter.cpp: In function 'void add(int, int, int, int, int, long long int)':
diameter.cpp:73:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   73 |     int mid = L + R >> 1;
      |               ~~^~~

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