【悬赏4个关注】why MLE?并查集find写挂了求调
查看原帖
【悬赏4个关注】why MLE?并查集find写挂了求调
539211
lzyqwq楼主2023/4/21 20:32
#include<bits/stdc++.h>
#define N 30005
using namespace std;
int cnt,n,m,w[N],dad[N],ans[N],f[N],sz[N],d[N],t[N],h[N],id[N],idx,bit[N];
vector<int>g[N];
string s;
struct operation{
    int op,u,v;
}q[N*10];
void debug(){
    if(++cnt>4e6){
        puts("lll");
        exit(0);
    }
}
int find(int x){
    debug();
    return dad[x]<0?x:dad[x]=find(dad[x]);
}
void merge(int x,int y){
    if(dad[x]>dad[y]){
        swap(x,y);
    }
    dad[x]+=dad[y];
    dad[y]=x;
}
void modify(int x,int k){
    for(int i=x;i<=n;i+=i&-i){
        bit[i]+=k;
    }
}
int query(int x){
    int ret=0;
    for(int i=x;i;i-=i&-i){
        ret+=bit[i];
    }
    return ret;
}
void dfs1(int u,int fa){
    sz[u]=1;
    for(int v:g[u]){
        if(v^fa){
            d[v]=d[u]+1;
            dfs1(v,f[v]=u);
            sz[u]+=sz[v];
        }
    }
}
void dfs2(int u,int fa){
    for(int v:g[u]){
        if(v^fa){
            if((sz[v]<<1)>sz[u]){
                t[h[u]=v]=t[u];
            }else{
                t[v]=v;
            }
            dfs2(v,u);
        }
    }
}
void dfs3(int u,int fa){
    modify(id[u]=++idx,w[u]);
    if(h[u]){
        dfs3(h[u],u);
    }
    for(int v:g[u]){
        if((v^fa)&&(v^h[u])){
            dfs3(v,u);
        }
    }
}
int pathquery(int x,int y){
    int ret=0;
    while(t[x]^t[y]){
        if(d[t[x]]<d[t[y]]){
            swap(x,y);
        }
        ret+=query(id[x])-query(id[t[x]]-1);
        x=f[t[x]];
    }
    if(d[x]>d[y]){
        swap(x,y);
    }
    return ret+query(id[y])-query(id[x]-1);
}
int main(){
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    memset(dad,-1,sizeof dad);
    cin>>n;
    for(int i=1;i<=n;++i){
        cin>>w[i];
    }
    cin>>m;
    for(int i=1,x,y;i<=m;++i){
        cin>>s>>q[i].u>>q[i].v;
        if(s[0]=='b'){
            q[i].op=0;
            if((x=find(q[i].u))^(y=find(q[i].v))){
                ans[i]=2;
                merge(x,y);
                g[q[i].u].emplace_back(q[i].v);
                g[q[i].v].emplace_back(q[i].u);
            }else{
                ans[i]=1;
            }
        }else if(s[0]^'e'){
            q[i].op=1;
        }else{
            q[i].op=2;
            if(find(q[i].u)^find(q[i].v)){
                ans[i]=3;
            }else{
                ans[i]=4;
            }
        }
    }
    for(int i=1;i<=n;++i){
        if(!sz[i]){
            dfs1(i,0);
            dfs2(t[i]=i,0);
            dfs3(i,0);
        }
    }
    for(int i=1;i<=m;++i){
        if(!q[i].op){
            cout<<(ans[i]==1?"no\n":"yes\n");
        }else if(q[i].op&1){
            modify(id[q[i].u],-w[q[i].u]);
            modify(id[q[i].u],w[q[i].u]=q[i].v);
        }else{
            if(ans[i]&1){
                cout<<"impossible\n";
            }else{
                cout<<pathquery(q[i].u,q[i].v)<<'\n';
            }
        }
    }
}
2023/4/21 20:32
加载中...