Submission #329204

#	Time	Username	Problem	Language	Result	Execution time	Memory
329204		Mahdi_Shokoufi	Dynamic Diameter (CEOI19_diameter)	C++17	100 / 100	477 ms	63940 KiB

diameter

//In The Name of Allah
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair < int , int > pii;
typedef pair < ll , ll > pll;

#define X first
#define Y second
#define mp make_pair
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x.size())
#define lc (2 * id)
#define rc (2 * id + 1)

const int N = 1e5 + 10;
const ll mod = 1e9 + 7;
const ll inf = 1e18 + 10;

struct node{
    ll a, b, ab, ba, res, lzy;
    node(){
        a = b = ab = ba = -inf;
        res = lzy = 0;
    }
};

ll a[2 * N], st[N], ft[N], H[N], T;
vector < pll > adj[N];
pair < pll , ll > E[N];
node seg[8 * N];

void dfs(ll v, ll p){
    st[v] = T ++;
    a[st[v]] = v;
    for (pll e : adj[v]){
        ll u = e.X, w = e.Y;
        if (u == p)
            continue;
        H[u] = H[v] + w;
        dfs(u, v);
        a[T ++] = v;
    }
    ft[v] = T;
}

node merge(node A, node B){
    node C;
    C.a = max(A.a, B.a);
    C.b = max(A.b, B.b);
    C.ab = max({A.ab, B.ab, A.a + B.b});
    C.ba = max({A.ba, B.ba, A.b + B.a});
    C.res = max({A.res, B.res, A.a + B.ba, A.ab + B.a});
    C.lzy = 0;
    return C;
}

void build(int l = 0, int r = T, int id = 1){
    if (r - l == 1){
        seg[id].a = H[a[l]];
        seg[id].b = -2LL * H[a[l]];
        seg[id].ab = seg[id].ba = -H[a[l]];
        return ;
    }
    int mid = (l + r) / 2;
    build(l, mid, lc);
    build(mid, r, rc);
    seg[id] = merge(seg[lc], seg[rc]);
}

void add(int id, ll x){
    seg[id].a += x;
    seg[id].b += -2LL * x;
    seg[id].ab += -x;
    seg[id].ba += -x;
    seg[id].lzy += x;
}

void shift(int id){
    ll x = seg[id].lzy;
    if (x == 0)
        return ;
    add(lc, x);
    add(rc, x);
    seg[id].lzy = 0;
}

void upd(int l, int r, ll x, int s = 0, int e = T, int id = 1){
    if (e <= l || r <= s)
        return ;
    if (l <= s && e <= r){
        add(id, x);
        return ;
    }
    shift(id);
    int mid = (s + e) / 2;
    upd(l, r, x, s, mid, lc);
    upd(l, r, x, mid, e, rc);
    seg[id] = merge(seg[lc], seg[rc]);
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    ll n, q, W;
    cin >> n >> q >> W;
    for (int i = 1; i < n; i ++){
        ll u, v, w;
        cin >> u >> v >> w;
        adj[u].pb(mp(v, w));
        adj[v].pb(mp(u, w));
        E[i] = mp(mp(u, v), w);
    }
    dfs(1, 0);
    build();
    ll last = 0;
    while (q --){
        ll x, y;
        cin >> x >> y;
        x = (x + last) % (n - 1) + 1;
        y = (y + last) % W;
        ll v = (H[E[x].X.X] < H[E[x].X.Y] ? E[x].X.Y : E[x].X.X);
        upd(st[v], ft[v], y - E[x].Y);
        E[x].Y = y;
        last = seg[1].res;
        cout << last << '\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