Submission #1302049

#	Time	Username	Problem	Language	Result	Execution time	Memory
1302049		AMel0n	Dynamic Diameter (CEOI19_diameter)	C++20	100 / 100	423 ms	55172 KiB

diameter

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
#define FOR(i,N) for(ll i = 0; i < N; i++)
#define all(x) (x).begin(), (x).end()
#define F first
#define S second

const ll INF = 1e18;

ll N, Q, W;

vector<vector<pair<ll,ll>>> adj;
vector<ll> id, wt;
vector<ll> in, out;

struct node {
    ll mn, mx, le, ri, bsf;
};
vector<node> tree;
vector<ll> lazy;

ll t = 0;
void dfs(ll v, ll p) {
    in[v] = t++;
    for(auto [u, i]: adj[v]) {
        if (u == p) continue;
        id[i] = u;
        dfs(u, v);
    }
    out[v] = t++;
}

node merge(node a, node b) {
    if (a.mn == INF) return b;
    if (b.mn == INF) return a;
    node res;
    res.mn = min(a.mn, b.mn);
    res.mx = max(a.mx, b.mx);
    res.le = max({a.le, b.le, a.mx - 2 * b.mn});
    res.ri = max({a.ri, b.ri, b.mx - 2 * a.mn});
    res.bsf = max({a.bsf, b.bsf, a.le + b.mx, b.ri + a.mx});
    return res;
}

void pushdown(ll tl, ll tr, ll i) {
    if (lazy[i]) {
        tree[i].mn += lazy[i];
        tree[i].mx += lazy[i];
        tree[i].le -= lazy[i];
        tree[i].ri -= lazy[i];
        if (tl != tr) {
            lazy[i * 2] += lazy[i];
            lazy[i * 2 + 1] += lazy[i];
        }
        lazy[i] = 0;
    }
}

void update(ll v, ll l, ll r, ll tl = 0, ll tr = N * 2 - 1, ll i = 1) {
    pushdown(tl, tr, i);
    if (l > r) return ;
    if (tl == l && tr == r) {
        lazy[i] += v;
        pushdown(tl, tr, i);
        return ;
    }
    ll tm = (tl + tr) / 2;
    update(v, l, min(r, tm), tl, tm, i * 2);
    update(v, max(l, tm + 1), r, tm + 1, tr, i * 2 + 1);
    tree[i] = merge(tree[i * 2], tree[i * 2 + 1]);
}

node query(ll l, ll r, ll tl = 0, ll tr = N * 2 - 1, ll i = 1) {
    pushdown(tl, tr, i);
    if (l > r) return {INF, -INF, -INF, -INF, -INF};
    if (tl == l && tr == r) return tree[i];
    ll tm = (tl + tr) / 2;
    return merge(query(l, min(r, tm), tl, tm, i * 2), query(max(l, tm + 1), r, tm + 1, tr, i * 2 + 1));
}


signed main() {
    cin.tie(0); ios::sync_with_stdio(false);
    cin >> N >> Q >> W;
    adj.resize(N), id.resize(N-1), wt.resize(N-1), in.resize(N), out.resize(N), lazy.resize(N*8), tree.resize(N*8);
    FOR(i, N-1) {
        ll a, b;
        cin >> a >> b >> wt[i];
        a--; b--;
        adj[a].push_back({b, i});
        adj[b].push_back({a, i});
    }

    dfs(0,0);

    FOR(i, N-1) {
        update(wt[i], in[id[i]], out[id[i]]-1);
    }

    ll last = 0;
    FOR(i, Q) {
        ll d, e;
        cin >> d >> e;
        d = (d + last) % (N-1);
        e = (e + last) % W;
        update(e - wt[d], in[id[d]], out[id[d]]-1);
        wt[d] = e;
        last = query(0, N*2-1).bsf;
        cout << last << endl;
    }
}

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