Submission #884744

#	Time	Username	Problem	Language	Result	Execution time	Memory
884744		Shayan86	Dynamic Diameter (CEOI19_diameter)	C++14	100 / 100	296 ms	55496 KiB

diameter

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

#pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
// Ofast, O0, O1, O2, O3, unroll-loops, fast-math, trapv

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

#define Mp          make_pair
#define sep         ' '
#define endl        '\n'
#define F	        first
#define S	        second
#define pb          push_back
#define all(x)      (x).begin(),(x).end()
#define kill(res)	cout << res << '\n', exit(0);
#define set_dec(x)	cout << fixed << setprecision(x);
#define fast_io     ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io     freopen("input.txt", "r", stdin) ; freopen("output.txt", "w", stdout);

#define lid (id*2)
#define rid (id*2+1)
#define mid ((l+r)/2)

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const ll N = 1e5 + 50;
const ll inf = -1e18;

ll n, q, W, w[N], down[N], st[N], ft[N];

vector<int> vec;
vector<pii> adj[N];

void dfs(int v, int p = 0){
    st[v] = vec.size(); vec.pb(v);
    for(auto [u, i]: adj[v]){
        if(u == p) continue;
        down[i] = u; dfs(u, v);
        vec.pb(v);
    }
    ft[v] = vec.size();
}

struct dt{
    ll mx, mn, lft, rit, dim;
    dt(ll a = 0, ll b = 0, ll c = 0, ll d = 0, ll e = 0){
        mx = a; mn = b; lft = c; rit = d; dim = e;
    }
    dt merg(dt x){
        dt out;
        out.mx = max(mx, x.mx);
        out.mn = min(mn, x.mn);
        out.lft = max({lft, x.lft, mx - 2 * x.mn});
        out.rit = max({rit, x.rit, x.mx - 2 * mn});
        out.dim = max({dim, x.dim, lft + x.mx, mx + x.rit});
        return out;
    }
};

dt seg[N*8]; ll lz[N*8];

void quex(int id, ll x){
    lz[id] += x;
    seg[id].mx += x;
    seg[id].mn += x;
    seg[id].lft -= x;
    seg[id].rit -= x;
}

void relax(int id){
    quex(lid, lz[id]);
    quex(rid, lz[id]);
    lz[id] = 0;
}

void upd(int ql, int qr, ll x, int l = 0, int r = vec.size(), int id = 1){
    if(ql <= l && r <= qr){
        quex(id, x); return;
    }
    if(qr <= l || r <= ql) return;

    relax(id);
    upd(ql, qr, x, l, mid, lid);
    upd(ql, qr, x, mid, r, rid);
    seg[id] = seg[lid].merg(seg[rid]);
}

dt get(int ql = 0, int qr = vec.size(), int l = 0, int r = vec.size(), int id = 1){
    if(ql <= l && r <= qr) return seg[id];
    if(qr <= l || r <= ql) return dt(-inf, inf, -inf, -inf, -inf);

    relax(id);
    return (get(ql, qr, l, mid, lid)).merg(get(ql, qr, mid, r, rid));
}

int main(){
    fast_io;

    cin >> n >> q >> W;

    int u, v;
    for(int i = 0; i < n-1; i++){
        cin >> u >> v >> w[i];
        adj[u].pb({v, i});
        adj[v].pb({u, i});
    }

    dfs(1);

    for(int i = 0; i < n-1; i++) upd(st[down[i]], ft[down[i]], w[i]);

    ll last = 0;
    while(q--){
        ll dj, djp, ej, ejp;

        cin >> dj >> ej;
        djp = (dj + last) % (n-1);
        ejp = (ej + last) % W;

        upd(st[down[djp]], ft[down[djp]], ejp - w[djp]); w[djp] = ejp;

        last = get().dim;
        cout << last << endl;
    }

}

Compilation message (stderr)

diameter.cpp: In function 'void dfs(int, int)':
diameter.cpp:40:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   40 |     for(auto [u, i]: adj[v]){
      |              ^

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