POI2012 Rendezvous 基环树+分类讨论

布满荆棘的人生 2021-11-23 23:10 183阅读 0赞

# POI2012 Rendezvous #

[题目传送][Link 1]

sol：

首先把连通块划分出来。

对于不在一个连通块的两点不能相会，否则必定能相会。

在一个连通块内的又需分情况考虑。

先把环给拎出来，则环上每个点挂着一棵子树（不算环上的点）。

如果两点在一棵子树，则直接求lca即可，路径唯一，二者步数也唯一。

如果两点不在一棵子树，则必然二者都需要先走到环上，

然后两点有两种方式可以相会，按照题目要求讨论即可。

细节有点多，仔细考虑清楚每一步该怎么写就好了。

尽量减少vector的直接调用，不然不开O2的情况下，常数巨大！

#include<bits/stdc++.h>
    #define IL inline
    #define RG register
    #define DB double
    #define LL long long
    #define pb push_back
    using namespace std;
    
    IL int gi() {
        RG int x=0,p=1; RG char ch=getchar();
        while(ch<'0'||ch>'9') {if(ch=='-') p=-1;ch=getchar();}
        while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
        return x*p;
    }
    
    const int N=5e5+3;
    
    vector<int> S[N],cir[N];
    int n,m,num,top,tot,a[N],in[N],id[N],cnt[N],vis[N],pos[N],dep[N],bel[N],sta[N],ins[N],head[N],f[N][20];
    
    struct path{int a,b;};
    struct EDGE{int next,to;}e[N<<1];
    
    IL void make(int a,int b) {e[++tot]=(EDGE){head[a],b},head[a]=tot;}
    
    IL void New_Graph() {
        tot=0;
        memset(&e,0,sizeof(e));
        memset(head,0,sizeof(head));
    }
    
    void Dfs(int x) {
        RG int i,y;
        vis[x]=1,pos[x]=num,S[num].pb(x);
        for(i=head[x];i;i=e[i].next)
            if(!vis[y=e[i].to]) Dfs(y);
    }
    
    void dfs(int x) {
        RG int i,y;
        for(i=head[x];i;i=e[i].next)
            if(!in[y=e[i].to])
                bel[y]=bel[x],f[y][0]=x,dep[y]=dep[x]+1,dfs(y);
    }
    
    IL void multiply(int Id) {
        RG int i,j,x;
        for(i=1;i<20;++i)
            for(j=0;j<S[Id].size();++j)
                x=S[Id][j],f[x][i]=f[f[x][i-1]][i-1];
    }
    
    IL path lca(int x,int y) {
        RG int i,fl=0,sx=0,sy=0;
        if(dep[x]<dep[y]) swap(x,y),fl=1;
        for(i=19;i>=0;--i)
            if(dep[f[x][i]]>=dep[y]) sx+=1<<i,x=f[x][i];
        if(x==y) return fl?(path){sy,sx}:(path){sx,sy};
        for(i=19;i>=0;--i)
            if(f[x][i]!=f[y][i]) sx+=1<<i,sy+=1<<i,x=f[x][i],y=f[y][i];
        return fl?(path){sy+1,sx+1}:(path){sx+1,sy+1};
    }
    
    void getcir(int x,int Id) {
        if(ins[x]) {
            RG int k;
            do{k=sta[top--],cir[Id].pb(k),in[k]=1,id[k]=++cnt[Id];}while(k!=x);
            return;
        }   
        sta[++top]=x,ins[x]=1,getcir(a[x],Id);
    }
    
    IL void getfore(int Id) {
        RG int i,x;
        for(i=0;i<cnt[Id];++i) 
            x=cir[Id][i],bel[x]=x,dep[x]=1,dfs(x);
        multiply(Id);
    }
    
    int main()
    {
        RG int i,x,y;
        n=gi(),m=gi();
        for(i=1;i<=n;++i) a[i]=gi(),make(i,a[i]),make(a[i],i);
        for(i=1;i<=n;++i)
            if(!vis[i]) ++num,Dfs(i);
        for(i=1,New_Graph();i<=n;++i) make(a[i],i);
        for(i=1;i<=num;++i)
            top=0,getcir(S[i][0],i),getfore(i);
        while(m--) {
            x=gi(),y=gi();
            if(pos[x]!=pos[y]) {puts("-1 -1");continue;}
            else {
                if(bel[x]==bel[y]) {
                    path s=lca(x,y);
                    printf("%d %d\n",s.a,s.b);
                }
                else {
                    int dx=bel[x],dy=bel[y],lx1,lx2,ly1,ly2,Mx1,Mx2,Mi1,Mi2;
                    ly1=dep[y]-1,lx2=dep[x]-1;
                    if(id[dx]<id[dy]) lx1=dep[x]-1+cnt[pos[x]]-id[dy]+id[dx],ly2=dep[y]-1+id[dy]-id[dx];
                    else lx1=dep[x]-1+id[dx]-id[dy],ly2=dep[y]-1+cnt[pos[x]]+id[dy]-id[dx];
                    Mx1=max(lx1,ly1),Mx2=max(lx2,ly2);
                    if(Mx1==Mx2) {
                        Mi1=min(lx1,ly1),Mi2=min(lx2,ly2);
                        if(Mi1==Mi2) printf("%d %d\n",Mx1,Mi1);
                        else if(Mi1<Mi2) printf("%d %d\n",lx1,ly1);
                        else printf("%d %d\n",lx2,ly2);
                    }
                    else if(Mx1<Mx2) printf("%d %d\n",lx1,ly1);
                    else printf("%d %d\n",lx2,ly2);                 
                }
            }
        }
        return 0;
    }

转载于:https://www.cnblogs.com/Bhllx/p/11253310.html

[Link 1]: https://www.luogu.org/problem/P3533