Submission #478141

#	Time	Username	Problem	Language	Result	Execution time	Memory
478141		bonopo	Dynamic Diameter (CEOI19_diameter)	C++17	100 / 100	3104 ms	121632 KiB

diameter

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC target ("avx2")
#define pb push_back
#define rc (i<<1)|1
#define lc (i<<1)
#define el "\n"
#define f first
#define s second

typedef long long ll;
const int MM=1e5+5, MOD=1e9+7, LOG=19;
int N, Q, sz[MM], bk[MM], pa[MM], in[LOG][MM], ot[LOG][MM], cp[LOG][MM], tp[LOG][MM], ct;
vector<pair<int,ll>> adj[MM]; ll av[MM], W; pair<ll,int> mp[MM];
multiset<ll> ast;

struct node {
    ll lz;
    pair<ll,int> mx;
};

struct tree {
    vector<node> seg;
    int wt, h;

    inline void apply(int i, ll v) {
        seg[i].mx.f+=v;
        if(i<wt) seg[i].lz+=v;
    }

    inline void build(int p) {
        while(p>1) p>>=1, seg[p].mx=max(seg[p<<1].mx, seg[p<<1|1].mx), seg[p].mx.f+=seg[p].lz;
    }

    inline void push(int p) {
        for(int s=h; s>0; --s) {
            int i=p>>s;
            if (seg[i].lz!=0) {
                apply(lc, seg[i].lz);
                apply(rc, seg[i].lz);
                seg[i].lz=0;
            }
        }
    }

    inline void inc(int l, int r, ll value) {
        if(l>r) return;
        r++; l+=wt, r+=wt; int l0=l, r0=r;
        for (; l<r; l>>=1, r>>=1) {
            if(l&1) apply(l++, value);
            if(r&1) apply(--r, value); }
        build(l0); build(r0 - 1);
    }

    inline pair<ll,int> qry(int l, int r) {
        if(l>r) return {0,0};
        r++; l+=wt, r+=wt; push(l); push(r - 1);
        pair<ll,int> res=make_pair(0,0);
        for (; l<r; l>>=1, r>>=1) {
            if(l&1) res=max(res, seg[l++].mx);
            if(r&1) res=max(seg[--r].mx, res); }
        return res;
    }

    inline void construct() {
        for (int i=wt-1; i>0; --i) seg[i].mx=max(seg[lc].mx, seg[rc].mx);
    }

    inline void init(int n) {
        wt=n; h=64-__builtin_clzll((ll)n);
        seg.resize(2*n+1);
        for(int i=n; i<n+n; ++i) seg[i].mx=mp[i-n+1];
        construct();
    }
} st[MM];

int crt(int u, int th, int fa) {
    for(auto &e:adj[u]) if(e.f!=fa&&!bk[e.f]&&sz[e.f]>th) {
        return crt(e.f, th, u); }
    return u;
}

void dfs(int u, int fa) {
    sz[u]=1;
    for(auto &e:adj[u]) if(e.f!=fa&&!bk[e.f]) {
        dfs(e.f, u); sz[u]+=sz[e.f];
    }
}

void etr(int u, int fa, int lvl, int rt, int tv, ll ew) {
    in[lvl][u]=++ct; cp[lvl][u]=rt; tp[lvl][u]=tv; mp[ct]=make_pair(ew,u);
    for(auto &e:adj[u]) if(e.f!=fa&&!bk[e.f]) {
        etr(e.f, u, lvl, rt, tv, e.s+ew); }
    ot[lvl][u]=ct;
}

void rec(int rt, int nds, int fa=-1, int lvl=0) {
    if(nds<=1) return; dfs(rt, 0);
    rt=crt(rt, nds/2, 0); pa[rt]=fa;
    bk[rt]=true; ct=0;

    // get ett
    cp[lvl][rt]=tp[lvl][rt]=rt;
    for(auto &e:adj[rt]) if(!bk[e.f]) etr(e.f, rt, lvl, rt, e.f, e.s);
    if(ct==0) return;

    // construct tree
    st[rt].init(ct);
    auto x=st[rt].qry(0, ct-1); x.s=tp[lvl][x.s];
    auto y=max(st[rt].qry(0, in[lvl][x.s]-2), st[rt].qry(ot[lvl][x.s], ct-1));
    ast.insert(av[rt]=x.f+y.f);

    int tally=0, lv=-1;
    for(auto &e:adj[rt]) if(!bk[e.f]) {
        if(sz[e.f]<sz[rt]) {
            tally+=sz[e.f];
            rec(e.f, sz[e.f], rt, lvl+1); }
        else lv=e.f; }
    if(~lv) rec(lv, nds-tally-1, rt, lvl+1);
}

void qry(int u, int v, ll val) {
    int cur=0;
    while(cur<LOG-1&&cp[cur+1][u]==cp[cur+1][v]&&cp[cur+1][u]!=0) ++cur;

    int crt=cp[cur][u];
    while(cur>=0) {
        int w=(in[cur][u]>in[cur][v]?u:v), wt=st[crt].wt;
        st[crt].inc(in[cur][w]-1, ot[cur][w]-1, val);

        auto x=st[crt].qry(0, wt-1); x.s=tp[cur][x.s];
        auto y=max(st[crt].qry(0, in[cur][x.s]-2), st[crt].qry(ot[cur][x.s], wt-1));

        ll cnd=x.f+y.f;
        if(cnd!=av[crt]&&st[crt].wt>0) {
            ast.erase(ast.find(av[crt]));
            ast.insert(av[crt]=cnd); }
        crt=pa[crt]; cur--;
    }
}

int32_t main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    cin>>N>>Q>>W;
    vector<pair<ll,pair<int,int>>> edg;
    for(int i=1; i<N; ++i) {
        ll u, v, w; cin>>u>>v>>w;
        adj[u].pb({v,w}); adj[v].pb({u,w});
        edg.pb({w,{u,v}}); }
    // preprocess
    rec(1, N);

    ll last=0, e, w;
    for(int q=1; q<=Q; ++q) {
        cin>>e>>w;
        e=(e+last)%(N-1);
        w=(w+last)%W;

        qry(edg[e].s.f, edg[e].s.s, w-edg[e].f);
        last=*ast.rbegin(); edg[e].f=w;
        cout<<last<<el;
    }
}

Compilation message (stderr)

diameter.cpp: In function 'void rec(int, int, int, int)':
diameter.cpp:102:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  102 |     if(nds<=1) return; dfs(rt, 0);
      |     ^~
diameter.cpp:102:24: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  102 |     if(nds<=1) return; dfs(rt, 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