Submission #478139

#	Time	Username	Problem	Language	Result	Execution time	Memory
478139		bonopo	Dynamic Diameter (CEOI19_diameter)	C++17	49 / 100	2840 ms	105884 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], mp[MM], ct;
vector<int> adj[MM]; ll av[MM], W;
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, int 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);
    }

    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 prop(int i, int l, int r) {
//        if(l!=r) {
//            seg[lc].lz+=seg[i].lz;
//            seg[rc].lz+=seg[i].lz; }
//        seg[i].mx.f+=seg[i].lz;
//        seg[i].lz=0;
//    }
//
//    void build(int i, int sl, int sr) {
//        if(sl==sr) {
//            seg[i].mx=make_pair(0,mp[sl]);
//            return; }
//        int m=sl+sr>>1;
//        build(rc, m+1, sr);
//        build(lc, sl, m);
//        calc(i);
//    }
//
//    inline void calc(int i) {
//        seg[i].mx=max(seg[lc].mx, seg[rc].mx);
//    }
//
//    void upd(int i, int sl, int sr, int l, int r, ll v) {
//        prop(i, sl, sr);
//        if(l>sr || r<sl) return;
//        if(l<=sl&&sr<=r) {
//            seg[i].lz+=v;
//            prop(i, sl, sr); return; }
//        int m=sl+sr>>1;
//        upd(rc, m+1, sr, l, r, v);
//        upd(lc, sl, m, l, r, v);
//        calc(i);
//    }
//
//    pair<ll,int> rmq(int i, int sl, int sr, int l, int r) {
//        if(l>sr || r<sl) return {0,0};
//        prop(i, sl, sr);
//        if(l<=sl&&sr<=r) return seg[i].mx;
//        int m=sl+sr>>1;
//        return max(rmq(lc, sl, m, l, r), rmq(rc, m+1, sr, l, r));
//    }

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

    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={0,mp[i-n+1]};
        construct();
    }
} st[MM];

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

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

void etr(int u, int fa, int lvl, int rt, int tv) {
    in[lvl][u]=++ct; cp[lvl][u]=rt; tp[lvl][u]=tv; mp[ct]=u;
    for(int &v:adj[u]) if(v!=fa&&!bk[v]) {
        etr(v, u, lvl, rt, tv); }
    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(int &v:adj[rt]) if(!bk[v]) etr(v, rt, lvl, rt, v);
    if(ct==0) return;

    // construct tree
    st[rt].init(ct);
    int tally=0, lv=-1;
    for(int &v:adj[rt]) if(!bk[v]) {
        if(sz[v]<sz[rt]) {
            tally+=sz[v];
            rec(v, sz[v], rt, lvl+1); }
        else lv=v; }
    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]) {
            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); adj[v].pb(u);
        edg.pb({w,{u,v}});
    }

    // preprocess
    rec(1, N);
    for(int i=1; i<=N; ++i) ast.insert(0);
    for(auto &e:edg) qry(e.s.f, e.s.s, e.f);

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