POI2012约会Rendezvous

题目描述

给定一个有 nnn 个顶点的有向图，每个顶点有且仅有一条出边。每次询问给出两个顶点 aia_ia​i​​ 和 bib_ib​i​​，求满足以下条件的 xix_ix​i​​ 和 yiy_iy​i​​：

• 从顶点 aia_ia​i​​ 沿出边走 xix_ix​i​​ 步与从顶点 bib_ib​i​​ 沿出边走 yiy_iy​i​​ 步到达的顶点相同。


• max(xi,yi)i​​,y​i​​) 最小。


• 满足以上条件的情况下 min(xi,yi)i​​,y​i​​) 最小。


• 如果以上条件没有给出一个唯一的解，则还需要满足 xi≥yii​​≥y​i​​.

如果不存在这样的 xi，yi，输出 -1 -1 ，i​​ 和 yiy_iy​i​​，则 xi=yi=−1x_i = y_i = -1x​i​​=y​i​​=−1.

输入格式

第一行两个正整数 n 和 k（1≤n≤500 000,1≤k≤500 000），表示顶点数和询问个数。

接下来一行 n 个正整数，第 iii 个数表示 iii 号顶点出边指向的顶点。

接下来 k 行表示询问，每行两个整数i​​ 和 bib_ib​i​​.

输出格式

对每组询问输出两个整数 xi，yi，i​​ 和 yiy_iy​i​​.

样例

样例输入

12 5
4 3 5 5 1 1 12 12 9 9 7 1
7 2
8 11
1 2
9 10
10 5

样例输出

2 3
1 2
2 2
0 1
-1 -1

数据范围与提示

对于 40% 的数据，n≤2000,k≤2000.

对于 100%100\%100% 的数据，1≤n≤500 000,1≤k≤500 000

　　　有向有环非联通图通常没什么素质。这题就是这样一个基环森林。。。。。首先要写一个对的LCA然后，可以用并查集来记录是否是一张图的，如果不是一张图上的直接-1 -1。在一张图上，用tarjan找到环（当然你有别的骚方法也没毛病），在环上的一圈点都有自己的子树，dfs的时候记录s[x]为x所在的子树，如果询问中两点在同一子树，直接LCA。如果不在，先找lca(x,s[x]),lca(y,s[y]);再找环上s[x]到s[y]的距离（我是通过选定环上任意一点开始dfs，然后记录每一点dep值，dep值的差和环的size-差是两种路径，根据题意优先级判断。然后就结束了

　　PS：（网站loj.ac上有这个题数据，不要问我怎么知道的）

#include
#include
#include
#include
#include
using namespace std;
const int N=500020;
int fr[N],s[N],size[N],stack[N],q[N],c[N],b[N],d[N],low[N],du[N],a[N],dfn[N],tp[N],pt[N],fa[N][20],num,cnt,kt,top,n,k,tt;
bool v[N],vs[N],ins[N];
struct node{int fr,to,pr;}mo[N];
struct qe{int a,b;};
int rd()
{
char cc=getchar();
int s=0,w=1;
while(cc<'0'||cc>'9') {if(cc=='-') w=-1;cc=getchar();}
while(cc>='0'&&cc<='9') s=(s<<3)+(s<<1)+cc-'0',cc=getchar();
return s*w;
}
bool cmp(int x,int y)
{
return du[x]>du[y];
}
void add(int x,int y)
{
mo[++tt].fr=x;
mo[tt].to=y;
mo[tt].pr=fr[x];
fr[x]=tt;du[x]++;
}
int find(int x)
{
if(x!=pt[x]) pt[x]=find(pt[x]);
return pt[x];
}
void merge(int x,int y)
{
x=find(x);y=find(y);
if(x!=y) pt[y]=x;
}
bool jud(int x,int y)
{
x=find(x);y=find(y);
return x==y;
}
void tarjan(int x)
{
low[x]=dfn[x]=++num;
stack[++top]=x;ins[x]=1;
for(int i=fr[x];i;i=mo[i].pr)
{
int y=mo[i].to;
if(!dfn[y])
{
tarjan(y);
low[x]=min(low[x],low[y]);
}
else if(ins[y]) low[x]=min(low[x],dfn[y]);
}
if(low[x]==dfn[x])
{
int y,s=0;++cnt;
int tmp=find(stack[top]);
do{
y=stack[top--];

size[cnt]++;
c[y]=cnt;
if(size[cnt]>1) b[tmp]=cnt,tp[tmp]=y;
ins[y]=0;
}while(x!=y);
}
}
void dfs(int x,int str)
{
v[x]=1;s[x]=str;
for(int i=1;i<=18;i++) fa[x][i]=fa[fa[x][i-1]][i-1];
for(int i=fr[x];i;i=mo[i].pr)
{
int to=mo[i].to;
if(v[to])continue;
fa[to][0]=x,d[to]=d[x]+1;
//cout< if(c[x]!=c[to]) dfs(to,str);
else dfs(to,to);
}
}
qe lca(int x,int y)
{
int ans1=0,ans2=0;
qe ans;
if(d[x] for(int i=18;~i;i--)
if(d[fa[x][i]]>=d[y]) x=fa[x][i],ans1+=(1< ans.a=ans1,ans.b=0;
if(x==y) return ans;
for(int i=18;~i;i--)
if(fa[x][i]!=fa[y][i])
x=fa[x][i],ans1+=(1< ans.a=ans1+1,ans.b=ans2+1;
return ans;
}
int main()
{
//freopen("ran3c.in","r",stdin);
//freopen("ran3c.ans","w",stdout);
n=rd();k=rd();
int x,y,tmp,rt;
for(int i=1;i<=n;i++) pt[i]=i,a[i]=i;
for(int i=1;i<=n;i++)
{
x=rd();
merge(x,i);
if(x==i) continue;
add(x,i);
}
for(int i=1;i<=n;i++) if(!dfn[i]) d[i]=1,tarjan(i);
for(int i=1;i<=n;i++) if(!vs[find(i)]) q[++kt]=find(i);
for(int i=1;i<=kt;i++) if(!v[q[i]]) d[q[i]]=1,dfs(q[i],q[i]);
//for(int i=1;i<=n;i++) printf("%d ",s[i]);
for(int i=1;i<=k;i++)
{
x=rd();y=rd();
if(!jud(x,y)) printf("-1 -1\n");
else
{
tmp=find(x);
if(s[x]==s[y])
{
qe te=lca(x,y);
if(d[x]>d[y])printf("%d %d\n",te.a,te.b);
else printf("%d %d\n",te.b,te.a);
}
else
{
int ans1=lca(x,s[x]).a,ans2=lca(y,s[y]).a,tmp1,tmp2;
x=s[x];y=s[y];
if(d[x] else tmp1=d[x]-d[y],tmp2=size[b[tmp]]-tmp1;
//cout< //for(int i=fr[93];i;i=mo[i].pr) cout<<1<<" ";
if(max(ans1+tmp1,ans2) else if(max(ans1+tmp1,ans2)>max(ans1,ans2+tmp2)) printf("%d %d\n",ans1,ans2+tmp2);
else
{
if(min(ans1+tmp1,ans2) else
{
if(min(ans1+tmp1,ans2)>min(ans1,ans2+tmp2)) printf("%d %d\n",ans1,ans2+tmp2);
else
{
if(ans1+tmp1>=ans2) printf("%d %d\n",ans1+tmp1,ans2);
else printf("%d %d\n",ans1,ans2+tmp2);
}
}
}
}
}
}
}
/*
g++ 1.cpp -o 1
./1
12 5
4 3 5 5 1 1 12 12 9 9 7 1
7 2
8 11
1 2
9 10
10 5
*/
View Code