Submission #478117

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
478117	2021-10-05T17:25:59 Z	bonopo	Dynamic Diameter (CEOI19_diameter)	C++17	7 / 100	5000 ms	66480 KB

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[LOG][MM], in[LOG][MM], ot[LOG][MM], cp[LOG][MM], tp[LOG][MM], ct;
vector<int> adj[MM]; ll av[MM];
multiset<ll> ast;
unordered_map<int,int> mp[MM];
 
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) {
        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};
        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) {
    dfs(rt, 0);
 
    // find centroid
  //  cout<<"centroid for "<<rt<<" nds "<<nds<<" lvl "<<lvl<<" is ";
    rt=crt(rt, nds/2, 0); pa[lvl][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);
 
    // construct tree
    st[rt].init(nds);
 
    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) {
        // 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[cur--][crt];
    }
 
}
 
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;
      //  cout<<"actual qry "<<e<<" "<<w<<el;
        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

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:53:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   53 |         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:62:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   62 |         int m=sl+sr>>1;
      |               ~~^~~

Subtask #1
0 / 11.0

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

Subtask #2
0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	9 ms	18764 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	9 ms	18764 KB	Output is correct
2	Correct	9 ms	18708 KB	Output is correct
3	Correct	10 ms	18768 KB	Output is correct
4	Correct	18 ms	18840 KB	Output is correct
5	Correct	54 ms	19164 KB	Output is correct
6	Correct	11 ms	18648 KB	Output is correct
7	Correct	13 ms	19000 KB	Output is correct
8	Correct	12 ms	18892 KB	Output is correct
9	Correct	11 ms	19004 KB	Output is correct
10	Correct	23 ms	19092 KB	Output is correct
11	Correct	86 ms	19356 KB	Output is correct
12	Correct	16 ms	21096 KB	Output is correct
13	Correct	16 ms	21068 KB	Output is correct
14	Correct	17 ms	21112 KB	Output is correct
15	Correct	35 ms	21264 KB	Output is correct
16	Correct	142 ms	21544 KB	Output is correct
17	Correct	172 ms	65840 KB	Output is correct
18	Correct	177 ms	65812 KB	Output is correct
19	Correct	173 ms	66040 KB	Output is correct
20	Correct	214 ms	66004 KB	Output is correct
21	Correct	312 ms	66480 KB	Output is correct