Submission #1156812

#	Time	Username	Problem	Language	Result	Execution time	Memory
1156812		Hamed_Ghaffari	Dynamic Diameter (CEOI19_diameter)	C++20	100 / 100	234 ms	54320 KiB

diameter

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

using ll  = long long;
using ld  = long double;
using pii = pair<int, int>;
using pll = pair<long long, long long>;
using ull = unsigned long long;

#define X               first
#define Y               second
#define SZ(x)           int(x.size())
#define all(x)          x.begin(), x.end()
#define mins(a,b)       (a = min(a,b))
#define maxs(a,b)       (a = max(a,b))
#define pb              push_back
#define Mp              make_pair
#define lc              id<<1
#define rc              lc|1
#define mid             ((l+r)/2)
mt19937_64              rng(chrono::steady_clock::now().time_since_epoch().count());

const ll  INF = 1e9 + 23;
const ll  MOD = 1e9 + 7;
const int MXN = 1e5 + 5;
const int LOG = 23;

struct Node {
    ll ans, pre, suf, mx, mn;
    Node() {
        ans = pre = suf = mx = -2e18;
        mn = 2e18;
    }
    friend Node merge(Node x, Node y) {
        Node res;
        res.ans = max({x.ans, y.ans, x.pre+y.mx, x.mx+y.suf});
        res.pre = max({x.pre, y.pre, x.mx-2*y.mn});
        res.suf = max({x.suf, y.suf, y.mx-2*x.mn});
        res.mx = max(x.mx, y.mx);
        res.mn = min(x.mn, y.mn);
        return res;
    }
} seg[MXN<<3];
ll lz[MXN<<3];

int n, q, stt[MXN], fnt[MXN], down[MXN];
ll W[MXN], ww;
vector<pii> g[MXN];
vector<int> tour;
ll h[MXN];

void Apply(ll x, int id) {
    seg[id].mn += x;
    seg[id].mx += x;
    seg[id].pre -= x;
    seg[id].suf -= x;
    lz[id] += x;
}
void Shift(int l, int r, int id) {
    if(r-l>1) {
        Apply(lz[id], lc);
        Apply(lz[id], rc);
    }
    lz[id] = 0;
}
void Build(int l=0, int r=2*n-1, int id=1) {
    if(r-l == 1) {
        seg[id].mn = seg[id].mx = h[tour[l]];
        return;
    }
    Build(l, mid, lc);
    Build(mid, r, rc);
    seg[id] = merge(seg[lc], seg[rc]);
}
void Upd(int s, int e, ll x, int l=0, int r=2*n-1, int id=1) {
    Shift(l, r, id);
    if(s<=l && r<=e) {
        Apply(x, id);
        return;
    }
    if(s<mid) Upd(s,e,x, l, mid, lc);
    if(e>mid) Upd(s,e,x, mid, r, rc);
    seg[id] = merge(seg[lc], seg[rc]);
}

void dfs(int v, int p=-1) {
    stt[v] = SZ(tour);
    tour.pb(v);
    for(auto [u, i] : g[v])
        if(u^p) {
            down[i] = u;
            h[u] = h[v]+W[i];
            dfs(u, v);
            tour.pb(v);
        }
    fnt[v] = SZ(tour);
}

void Main() {
    cin >> n >> q >> ww;
    for(int i=0; i<n-1; i++) {
        int u,v;
        ll w;
        cin >> u >> v >> w;
        g[u-1].pb(Mp(v-1, i));
        g[v-1].pb(Mp(u-1, i));
        W[i] = w;
    }
    dfs(0);
    Build();
    ll last=0;
    while(q--) {
        ll d, e;
        cin >> d >> e;
        (d += last) %= n-1;
        (e += last) %= ww;
        Upd(stt[down[d]], fnt[down[d]], -W[d]+e); W[d]=e;
        cout << (last=max(seg[1].ans, seg[1].mx)) << '\n';
    }
}

int32_t main() {
    cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
    int T = 1;
    // cin >> T;
    while(T--) Main();
    return 0;
}

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