Submission #939143

#	Time	Username	Problem	Language	Result	Execution time	Memory
939143		Amirreza_Fakhri	Dynamic Diameter (CEOI19_diameter)	C++17	100 / 100	211 ms	53484 KiB

diameter

// In the name of the God
#include <bits/stdc++.h>
#define ll long long
#define int long long
#define pb push_back
#define F first
#define S second
#define mp make_pair
#define pii pair <int, int>
#define smin(x, y) (x) = min((x), (y))
#define smax(x, y) (x) = max((x), (y))
#define all(x) (x).begin(), (x).end()
using namespace std;

// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2")

const int inf = 1e9+7;
const int mod = 998244353;
const int maxn = 1e5+5;

struct D {
    int sum, ans, mx, mn, vl, lv;
} seg[maxn*8];

int n, q, W, w[maxn], in[maxn], out[maxn];
vector <int> vec;
vector <pii> adj[maxn];

void dfs(int v = 0, int p = 0) {
    for (pii e : adj[v]) {
        if (e.F != p) {
            in[e.S] = vec.size(); vec.pb(w[e.S]);
            dfs(e.F, v);
            out[e.S] = vec.size(); vec.pb(-w[e.S]);
        }
    }
}

void relax(int id, int x) {
    seg[id].sum = x;
    seg[id].ans = abs(x);
    seg[id].mx = max(0ll, x);
    seg[id].mn = min(0ll, x);
    seg[id].vl = max(0ll, -2*x);
    seg[id].lv = max(0ll, x);
}

D merge(D l, D r) {
    D res;
    r.mx += l.sum, r.mn += l.sum, r.vl -= l.sum, r.lv -= l.sum;
    res.sum = l.sum+r.sum;
    res.ans = max(max(l.ans, r.ans), max(l.vl+r.mx, l.mx+r.lv));
    res.mx = max(l.mx, r.mx);
    res.mn = min(l.mn, r.mn);
    res.vl = max(max(l.vl, r.vl), l.mx-r.mn*2);
    res.lv = max(max(l.lv, r.lv), -l.mn*2+r.mx);
    return res;
}

void build(int l = 0, int r = 2*n-2, int id = 1) {
    if (l+1 == r) {
        relax(id, vec[l]); return;
    }
    int mid = (l+r)/2;
    build(l, mid, id*2), build(mid, r, id*2+1);
    seg[id] = merge(seg[id*2], seg[id*2+1]);
}

void upd(int i, int x, int l = 0, int r = 2*n-2, int id = 1) {
    if (l+1 == r) {
        relax(id, x); return;
    }
    int mid = (l+r)/2;
    if (i < mid) upd(i, x, l, mid, id*2);
    else upd(i, x, mid, r, id*2+1);
    seg[id] = merge(seg[id*2], seg[id*2+1]);
}

int32_t main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> q >> W;
    for (int i = 0; i < n-1; i++) {
        int v, u; cin >> v >> u >> w[i];
        adj[--v].pb(mp(--u, i));
        adj[u].pb(mp(v, i));
    }
    dfs(); build();
    int last = 0;
    while (q--) {
        int d, e; cin >> d >> e;
        d = (d+last)%(n-1), e = (e+last)%W;
        upd(in[d], e), upd(out[d], -e);
        cout << (last = seg[1].ans) << '\n';
    }
    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