zcmimi's blog
avatar
zc
2020-10-15 22:15:41
  • 本文总阅读量

查看原题

点击跳转

首先可以用并查集判断每个1操作是否有效

接下来很容易可以想到树剖+线段树优化建图

很可惜,出题人卡了这种大常数做法

考虑直接在树上倍增优化建图

和倍增lca差不多,一直向上连边

而每个点又拆为入点和出点

每次构建传送门时新建一个点,

连边时只需要[u_1,v_1]所在的块出点连接新建点,新建点连接[u_2,v_2]所在的块入点

详细见代码

#include<bits/stdc++.h>
const int N=500011,M=3000011;
int n,m,s,fa[N],tt;
int gf(int x){return x==fa[x]?x:fa[x]=gf(fa[x]);}
int cnt,head[M];
struct edge{int to,nxt,w;}e[1000011];
void add(int x,int y,int w){if(x&&y)e[++cnt].to=y,e[cnt].nxt=head[x],head[x]=cnt,e[cnt].w=w;}
#define fl(i,x) for(int i=head[x],to;to=e[i].to,i;i=e[i].nxt)
struct link{int u1,v1,u2,v2,w;}E[1000011];
int f[17][N],d[M];
void dfs(int x){fl(i,x)if(to!=f[0][x]&&to)d[to]=d[x]+1,f[0][to]=x,dfs(to);}
int lca(int x,int y){
    if(d[x]<d[y])x^=y^=x^=y;
    for(int i=15;~i;--i)if(d[f[i][x]]>=d[y])x=f[i][x];
    if(x==y)return x;
    for(int i=15;~i;--i)if(f[i][x]!=f[i][y])x=f[i][x],y=f[i][y];
    return f[0][x];
}
int id1[17][N],id2[17][N],nn;
void lk(int t,int u,int v,int w){
    if(u==v)return t?add(u,nn,w):add(nn,u,w);
    int i=0;for(;i<15&&f[i+1][u]&&d[f[i+1][u]]>=d[v]-1;++i);
    if(t)add(id2[i][u],nn,w);else add(nn,id1[i][u],w);
    if(f[i][u]!=f[0][v]){
        int dep=d[f[i][u]]-d[v]+1;
        for(int j=15;~j;--j)if(dep>>j&1)u=f[j][u];
        if(t)add(id2[i][u],nn,w);else add(nn,id1[i][u],w);
    }
}
struct node{int x,d;bool operator<(const node&t)const{return d>t.d;}};
static std::priority_queue<node>q;
bool v[M];
void dij(){
    memset(d,0x3f,sizeof d);
    q.push((node){s,d[s]=0});
    while(!q.empty()){
        int x=q.top().x;q.pop();
        if(v[x])continue;else v[x]=1;
        fl(i,x)if(d[x]+e[i].w<d[to])
            d[to]=d[x]+e[i].w,q.push((node){to,d[to]});
    }
}
int main(){
    scanf("%d%d%d",&n,&m,&s);
    int opt,u,v,u1,v1,u2,v2,w;
    for(int i=1;i<=n;++i)fa[i]=i;
    while(m--){
        scanf("%d",&opt);
        if(opt==1){
            scanf("%d%d%d%d%d",&u1,&v1,&u2,&v2,&w);
            if(gf(u1)==gf(v1)&&gf(u2)==gf(v2))E[++tt]=(link){u1,v1,u2,v2,w};
        }
        else{
            scanf("%d%d%d",&u,&v,&w);
            if(gf(u)!=gf(v))fa[gf(u)]=gf(v),add(u,v,w),add(v,u,w);
        }
    }
    for(int i=1;i<=n;++i)if(i==gf(i))dfs(i);
    nn=n;
    for(int i=1;i<=n;++i)id1[0][i]=id2[0][i]=i;
    for(int i=1;i<=15;++i)for(int j=1;j<=n;++j){
        f[i][j]=f[i-1][f[i-1][j]];
        if(id1[i-1][j]||id1[i-1][f[i-1][j]]){
            id1[i][j]=++nn,id2[i][j]=++nn;
            add(id1[i][j],id1[i-1][j],0),add(id2[i-1][j],id2[i][j],0);
            add(id1[i][j],id1[i-1][f[i-1][j]],0),add(id2[i-1][f[i-1][j]],id2[i][j],0);
        }
    }
    for(int i=1,l;i<=tt;++i){
        ++nn;
        u=E[i].u1,v=E[i].v1,w=E[i].w,l=lca(u,v);
        lk(1,u,l,w);lk(1,v,l,w);
        u=E[i].u2,v=E[i].v2,l=lca(u,v);
        lk(0,u,l,0);lk(0,v,l,0);
    }
    dij();
    for(int i=1;i<=n;++i)printf("%d ",d[i]==0x3f3f3f3f?-1:d[i]);
}
LG 5344 【XR-1】逛森林
comment评论
Search
search