Submission #1150726

#	Time	Username	Problem	Language	Result	Execution time	Memory
1150726		Warinchai	Grapevine (NOI22_grapevine)	C++20	0 / 100	307 ms	80640 KiB

Main

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,q;
vector<int>adj[200005];
int w[800005];
int have[800005];
map<pair<int,int>,int>mp;
int inf=1e9+5;
struct path{
    int mn,dis;
    path(int x=inf,int d=0){
        mn=x;
        dis=d;
    }
    friend path operator+(path a,path b){
        return path(min(a.mn,b.mn+a.dis),a.dis+b.dis);
    }
}paths[800005],rpaths[800005];
struct point{
    int mn;
    point(int x=inf){
        mn=x;
    }
    friend point operator+(point a,point b){
        return point(min(a.mn,b.mn));
    }
}points[800005];
path compress(path a,path b){
    return a+b;
}
path add_vertex(point x,int i){
    return path(min(x.mn+w[i],have[i]),w[i]);
}
path vertex(int i){
    return path(have[i],w[i]);
}
point rake(point a,point b){
    return a+b;
}
point add_edge(path x){
    return point(x.mn);
}
struct stttree{
    int hv[200005],sz[200005],type[800005],l[800005],r[800005],p[800005],pa[200005],id,rt;
    void dfs(int u,int p){
        //cerr<<"dfs:"<<u<<"\n";
        sz[u]=1;
        pa[u]=p;
        for(auto x:adj[u])if(x!=p){
            dfs(x,u);
            sz[u]+=sz[x];
            if(sz[x]>sz[hv[u]])hv[u]=x;
        }
    }
    void build(int u){
        dfs(u,0);
        id=2*n-1;
        rt=compress(u).first;
    }
    int add(int u,int lch,int rch,int t){
        if(!u)u=++id;
        if(lch)p[lch]=u;
        if(rch)p[rch]=u;
        l[u]=lch,r[u]=rch,type[u]=t;
        return u;
    }
    pair<int,int>merge(vector<pair<int,int>>v,int t){
        if(v.size()==1)return v[0];
        vector<pair<int,int>>l,r;
        int sz=0;
        for(auto x:v)sz+=x.second;
        for(auto x:v){
            if(sz>=x.second)l.push_back(x);
            else r.push_back(x);
            sz-=2*x.second;
        }
        auto ll=merge(l,t);
        auto rr=merge(r,t);
        return {add(0,ll.first,rr.first,t),ll.second+rr.second};
    }
    pair<int,int>compress(int u){
        vector<pair<int,int>>v;
        for(;u;u=hv[u])v.push_back(add_vertex(u));
        return merge(v,1);
    }
    pair<int,int>add_vertex(int u){
        pair<int,int>x=rake(u);
        return {add(u,x.first,0,x.first?2:3),x.second+1};
    }
    pair<int,int>rake(int u){
        vector<pair<int,int>>v;
        for(auto x:adj[u])if(x!=pa[u]&&x!=hv[u])v.push_back(add_edge(x));
        return v.empty()?make_pair(0LL,0LL):merge(v,4);
    }
    pair<int,int>add_edge(int u){
        pair<int,int>x=compress(u);
        return {add(0,x.first,0,5),x.second};
    }
}tr;
point rec(int u){
    path above,below;
    int p=tr.p[u];
    while(tr.type[p]==1){
        if(tr.l[p]==u)below=below+paths[tr.r[p]];
        else above=above+rpaths[tr.l[p]];
        u=p;
        p=tr.p[u];
    }
    if(p){
        u=p;
        p=tr.p[u];
        point temp;
        while(tr.type[p]==4){
            temp=temp+points[(tr.l[p]==u?tr.r[p]:tr.l[p])];
            u=p;
            p=tr.p[u];
        }
        temp=temp+rec(p);
        path x=add_vertex(temp,p);
        above=above+x;
    }
    return point(above.mn)+point(below.mn);
}
int reroot(int u){
    point temp;
    if(tr.type[u]==2)temp=temp+points[tr.l[u]];
    temp=temp+rec(u);
    return add_vertex(temp,u).mn;
}
void upd(int u,int t){
    //cerr<<"u:"<<u<<" ";
    if(t==1){
        paths[u]=compress(paths[tr.l[u]],paths[tr.r[u]]);
        rpaths[u]=compress(rpaths[tr.r[u]],rpaths[tr.l[u]]);
        //cerr<<paths[u].mn<<" "<<paths[u].dis<<"\n";
    }else if(t==2){
        paths[u]=rpaths[u]=add_vertex(points[tr.l[u]],u);
        //cerr<<paths[u].mn<<" "<<paths[u].dis<<"\n";
    }else if(t==3){
        paths[u]=rpaths[u]=vertex(u);
        //cerr<<paths[u].mn<<" "<<paths[u].dis<<"\n";
    }else if(t==4){
        points[u]=rake(points[tr.l[u]],points[tr.r[u]]);
        //cerr<<points[u].mn<<"\n";
    }else{
        points[u]=point(paths[tr.l[u]].mn);
        //cerr<<points[u].mn<<"\n";
    }
}
void dfs(int u){
    //cerr<<"u:"<<u<<" "<<tr.type[u]<<" "<<tr.l[u]<<" "<<tr.r[u]<<"\n";
    if(tr.l[u])dfs(tr.l[u]);
    if(tr.r[u])dfs(tr.r[u]);
    upd(u,tr.type[u]);
}
int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>q;
    for(int i=1;i<=8*n;i++)have[i]=inf;
    for(int i=1;i<n;i++){
        int a,b,ww;cin>>a>>b>>ww;
        adj[a].push_back(n+i);
        adj[n+i].push_back(a);
        adj[n+i].push_back(b);
        adj[b].push_back(n+i);
        w[n+i]=ww;
        mp[{a,b}]=mp[{b,a}]=i+n;
        //cerr<<a<<" "<<i+n<<" "<<b<<"\n";
    }
    tr.build(1);
    dfs(tr.rt);
    //cerr<<"\n\n";
    for(int i=0;i<q;i++){
        int t;cin>>t;
        if(t==1){
            int q;cin>>q;
            int ans=reroot(q);
            cout<<(ans==inf?-1:ans)<<"\n";
        }else if(t==2){
            int u;cin>>u;
            if(have[u]==0)have[u]=inf;
            else have[u]=0;
            for(;u;u=tr.p[u])upd(u,tr.type[u]);
            //cerr<<"\n\n";
        }else{
            int a,b,ww;cin>>a>>b>>ww;
            int u=mp[{a,b}];
            w[u]=ww;
            for(;u;u=tr.p[u])upd(u,tr.type[u]);
            //cerr<<"\n\n";
        }
    }
}

• Subtask 1: 0 / 6
• Subtask 2: 0 / 14
• Subtask 3: 0 / 15
• Subtask 4: 0 / 15
• Subtask 5: 0 / 18
• Subtask 6: 0 / 32