Submission #478135

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
478135	2021-10-05T19:39:38 Z	bonopo	Dynamic Diameter (CEOI19_diameter)	C++17	7 / 100	3738 ms	194820 KB

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<int> adj[MM]; ll av[MM], W;
gp_hash_table<int,int> mp[MM];
multiset<ll> ast;

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

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

    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,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) {
        if(l>sr || r<sl) return;
        prop(i, sl, sr);
        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 make_pair(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));
    }

    inline 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) {
    if(nds<=1) return; dfs(rt, 0);
    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);
    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) {

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

    int crt=cp[cur][u];
    while(cur>=0) {
        // cout<<"crt "<<crt<<el;
        int w=(in[cur][u]>in[cur][v]?u:v);

        // 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;
        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

diameter.cpp: In member function 'void tree::build(int, int, int)':
diameter.cpp:43:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   43 |         int m=sl+sr>>1;
      |               ~~^~~
diameter.cpp: In member function 'void tree::upd(int, int, int, int, int, ll)':
diameter.cpp:59:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   59 |         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:69:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   69 |         int m=sl+sr>>1;
      |               ~~^~~
diameter.cpp: In function 'void rec(int, int, int, int)':
diameter.cpp:101:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  101 |     if(nds<=1) return; dfs(rt, 0);
      |     ^~
diameter.cpp:101:24: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  101 |     if(nds<=1) return; dfs(rt, 0);
      |                        ^~~

Subtask #1
0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	21 ms	26956 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	21 ms	26956 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #3
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	22 ms	26956 KB	Output is correct
2	Correct	24 ms	26904 KB	Output is correct
3	Correct	23 ms	26988 KB	Output is correct
4	Correct	30 ms	27028 KB	Output is correct
5	Correct	67 ms	27332 KB	Output is correct
6	Correct	22 ms	26884 KB	Output is correct
7	Correct	24 ms	27036 KB	Output is correct
8	Correct	24 ms	27096 KB	Output is correct
9	Correct	29 ms	27156 KB	Output is correct
10	Correct	42 ms	27212 KB	Output is correct
11	Correct	100 ms	27460 KB	Output is correct
12	Correct	28 ms	28200 KB	Output is correct
13	Correct	29 ms	28236 KB	Output is correct
14	Correct	28 ms	28264 KB	Output is correct
15	Correct	50 ms	28264 KB	Output is correct
16	Correct	126 ms	28724 KB	Output is correct
17	Correct	156 ms	51424 KB	Output is correct
18	Correct	158 ms	51208 KB	Output is correct
19	Correct	161 ms	51116 KB	Output is correct
20	Correct	193 ms	51308 KB	Output is correct
21	Correct	283 ms	51752 KB	Output is correct