POI2012 Rendezvous

题目传送

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;
}