Submission #478129

#	Time	Username	Problem	Language	Result	Execution time	Memory
478129		bonopo	Dynamic Diameter (CEOI19_diameter)	C++17	49 / 100	5067 ms	203396 KiB

diameter

#include "bits/stdc++.h"
using namespace std;
#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, W, sz[MM], bk[MM], pa[MM], in[LOG][MM], ot[LOG][MM], cp[LOG][MM], tp[LOG][MM], ct;
vector<int> adj[MM]; ll av[MM];
unordered_map<int,int> mp[MM];
multiset<ll> ast;

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

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

    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={0,sl};
            return; }
        int m=sl+sr>>1;
        build(rc, m+1, sr);
        build(lc, sl, m);
        calc(i);
    }

    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) {
        prop(i, sl, sr);
        if(l>sr || r<sl) return {0,0};
        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 init(int n) {
        wt=n;
        seg.resize(4*n+4);
        build(1, 1, n);
    }
} 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[rt][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) {
    assert(lvl<LOG);
    dfs(rt, 0);

    // find centroid
    //  cout<<"centroid for "<<rt<<" nds "<<nds<<" lvl "<<lvl<<" is ";
    rt=crt(rt, nds/2, 0); pa[rt]=fa;
    //  cout<<rt<<el;

    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(nds);
    dfs(rt, 0);

    for(int &v:adj[rt]) if(!bk[v]) {
        rec(v, sz[v], rt, lvl+1);
    }
}

void qry(int u, int v, ll val) {

    // find smallest component
    int cur=0;
    while(cur<LOG-1&&cp[cur+1][u]!=0) ++cur;
    //  cout<<"iterating on "<<u<<" starting with "<<cur<<" delta "<<val<<el;

    // jump
    int crt=u;
    while(cur>=0) {
        // update edge
        //   cout<<"crt "<<crt<<el;

        if(cp[cur][u]==crt&&cp[cur][v]==crt) {
            int w=(in[cur][u]>in[cur][v]?u:v);
            ast.erase(ast.find(av[crt]));

            // cout<<"level "<<cur<<" w "<<w<<" cent "<<crt<<" updating "<<in[cur][w]<<" "<<ot[cur][w]<<el;
            st[crt].upd(1, 1, st[crt].wt, in[cur][w], ot[cur][w], val);

            // query max
            auto x=st[crt].rmq(1, 1, st[crt].wt, 1, st[crt].wt);
            x.s=mp[crt][x.s];
            // cout<<"x value "<<x.f<<" "<<x.s<<" "<<tp[cur][x.s]<<" "<<in[cur][tp[cur][x.s]]<<" "<<ot[cur][tp[cur][x.s]]<<el;
            auto y=max(st[crt].rmq(1, 1, st[crt].wt, 1, in[cur][tp[cur][x.s]]-1), st[crt].rmq(1, 1, st[crt].wt, ot[cur][tp[cur][x.s]]+1, st[crt].wt));
            //cout<<"y value "<<y.f<<" "<<x.s<<el;

            ll cnd=x.f+y.f; av[crt]=cnd;
            ast.insert(av[crt]);
        }

        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;
    memset(pa, -1, sizeof(pa));
    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;
    }
}

// MM

Compilation message (stderr)

diameter.cpp: In member function 'void tree::build(int, int, int)':
diameter.cpp:38:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   38 |         int m=sl+sr>>1;
      |               ~~^~~
diameter.cpp: In member function 'void tree::upd(int, int, int, int, int, ll)':
diameter.cpp:54:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   54 |         int m=sl+sr>>1;
      |               ~~^~~
diameter.cpp: In member function 'std::pair<long long int, int> tree::rmq(int, int, int, int, int)':
diameter.cpp:64:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   64 |         int m=sl+sr>>1;
      |               ~~^~~

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