Submission #1165185

#	Time	Username	Problem	Language	Result	Execution time	Memory
1165185		Warinchai	Dynamic Diameter (CEOI19_diameter)	C++20	24 / 100	665 ms	1114112 KiB

diameter

#include<bits/stdc++.h>
#define int long long
using namespace std;
vector<int>adj[200005];
int ar[200005];
int n,q,w;
struct path{
    int l,d,mxpre,mxsuf;
    path(int x=0){
        l=d=mxpre=mxsuf=x;
    }
    friend path operator+(path a,path b){
        path c;
        c.l=a.l+b.l;
        c.mxsuf=max(b.mxsuf,a.mxsuf+b.l);
        c.mxpre=max(a.mxpre,b.mxpre+a.l);
        c.d=max({a.d,b.d,a.mxsuf+b.mxpre});
        return c;
    }
}paths[800005];
struct point{
    int mx,d;
    point(int x=0){
        mx=d=x;
    }
    friend point operator+(point a,point b){
        point c;
        c.mx=max(a.mx,b.mx);
        c.d=max({a.d,b.d,a.mx+b.mx});
        return c;
    }
}points[800005];
struct sttttree{
    int sz[200005],hv[200005],l[200005],r[200005],p[200005],type[200005],pa[200005];
    int cur=0,rt;
    void dfs(int u,int p){
        pa[u]=p;
        sz[u]=1;
        for(auto x:adj[u]){
            if(x==p)continue;
            dfs(x,u);
            sz[u]+=sz[x];
            if(sz[x]>sz[hv[u]])hv[u]=x;
        }
    }
    void build(int x){
        dfs(x,0);
        cur=n+n-1;
        rt=compress(x).first;
    }
    int add(int t,int lch,int rch,int ty){
        if(t==0)t=++cur;
        type[t]=ty;
        //cerr<<t<<" "<<lch<<"\n";
        if(lch)p[lch]=t;
        if(rch)p[rch]=t;
        l[t]=lch,r[t]=rch;
        return t;
    }
    pair<int,int>merge(vector<pair<int,int>>&v,int type){
        if(v.size()==1)return v[0];
        int sz=0;
        vector<pair<int,int>>l,r;
        for(auto x:v){
            sz+=x.second;
        }
        for(auto x:v){
            if(x.second<=sz)l.push_back(x);
            else r.push_back(x);
            sz-=2*x.second;
        }
        auto a=merge(l,type);
        auto b=merge(r,type);
        l.clear();
        r.clear();
        return {add(0,a.first,b.first,type),a.second+b.second};
    }
    pair<int,int>compress(int x){
        //cerr<<"compress:"<<x<<"\n";
        vector<pair<int,int>>v;
        for(;x;x=hv[x])v.push_back(add_vertex(x));
        //for(auto x:v)cerr<<x.first<<" "<<x.second<<"\n";
        //cerr<<"compress con:"<<v[0].first<<"\n";
        return merge(v,1);
    }
    pair<int,int>add_vertex(int x){
        //cerr<<"add_vertex:"<<x<<"\n";
        pair<int,int>v=rake(x);
        //cerr<<"add vertex con:"<<v.first<<" "<<v.second<<"\n";
        pair<int,int>ans={add(x,v.first,0,v.second==0?3:2),v.second+1};
        //cerr<<"added ver:"<<ans.first<<" "<<ans.second<<"\n";
        return ans;
    }
    pair<int,int>rake(int x){
        //cerr<<"rake:"<<x<<"\n";
        vector<pair<int,int>>v;
        for(auto a:adj[x])if(a!=hv[x]&&a!=pa[x])v.push_back(add_edge(a));
        if(v.size()==0)return {0,0};
        return merge(v,4);
    }
    pair<int,int>add_edge(int x){
        //cerr<<"add edge"<<x<<"\n";
        pair<int,int>v=compress(x);
        return {add(0,v.first,0,5),v.second};
    }
}tr;
path compress(path a,path b){
    return a+b;
}
path add_vertex(point x,int val){
    path a;
    a.l=val;
    a.mxpre=a.mxsuf=x.mx+val;
    a.d=max(x.d,val+x.mx);
    return a;
}
path vertex(int x){
    path a(x);
    return a;
}
point rake(point a,point b){
    return a+b;
}
point add_edge(path a){
    point x;
    x.mx=a.mxpre,x.d=a.d;
    return x;
}
void upd(int u,int t){
    if(t==1){
        paths[u]=compress(paths[tr.l[u]],paths[tr.r[u]]);
    }else if(t==2){
        paths[u]=add_vertex(points[tr.l[u]],ar[u]);
    }else if(t==3){
        paths[u]=vertex(ar[u]);
    }else if(t==4){
        points[u]=rake(points[tr.l[u]],points[tr.r[u]]);
    }else{
        points[u]=add_edge(paths[tr.l[u]]);
    }
}
void change(int u){
    for(;u;u=tr.p[u])upd(u,tr.type[u]);
}
void dfs(int u){
    if(tr.l[u])dfs(tr.l[u]);
    if(tr.r[u])dfs(tr.r[u]);
    upd(u,tr.type[u]);
    //cout<<u<<" ";
    /*if(tr.type[u]<=3){
        cout<<"paths:"<<paths[u].d<<" "<<paths[u].l<<" "<<paths[u].mxpre<<" "<<paths[u].mxsuf<<"\n";
    }else{
        cout<<"points:"<<points[u].d<<" "<<points[u].mx<<"\n";
    }
    if(u==11)cout<<"11:"<<tr.l[u]<<" "<<tr.r[u]<<" "<<tr.type[u]<<"\n";*/
}
int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>q>>w;
    int cur=n;
    for(int i=1;i<n;i++){
        int a,b,c;cin>>a>>b>>c;
        adj[a].push_back(++cur);
        adj[cur].push_back(a);
        adj[b].push_back(cur);
        adj[cur].push_back(b);
        ar[cur]=c;
    }
    //cerr<<"work\n";
    tr.build(1);
    //printt(tr.rt);
    //cerr<<"work\n";
    dfs(tr.rt);
    //cerr<<"ANS:\n";
    //cerr<<paths[tr.rt].d<<"\n";
    int last=0;
    //cerr<<"still work\n";
    for(int i=0;i<q;i++){
        int d,e;cin>>d>>e;
        d=(d+last)%(n-1);
        e=(e+last)%w;
        ar[d+n+1]=e;
        change(d+n+1);
        //dfs(tr.rt);
        cout<<(last=paths[tr.rt].d)<<"\n";
    }
}

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