约会 Rendezvous

内存限制：128 MiB 时间限制：1000 ms 标准输入输出

题目描述

给定一个有 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)\max(x_i, y_i)max(x​i​​,y​i​​) 最小。
• 满足以上条件的情况下 min(xi,yi)\min(x_i, y_i)min(x​i​​,y​i​​) 最小。
• 如果以上条件没有给出一个唯一的解，则还需要满足 xi≥yix_i \ge y_ix​i​​≥y​i​​.

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

Q：这题是不是非常简单？

A：毒瘤题。

Q：毒瘤出题人？

A：毒瘤出题人。

Q：是不是比较考验码力，打完想对就能A？

A：毒瘤卡常，你没有一点卡常技巧是过不了的。

Q：我卡卡常就能A了是吗？

A：卡dfs 卡你空间，卡你时间，还特别容易爆栈 你需要特别的姿势！

34个测试点，让你绝望

没有看题解过了的毒瘤题

对于我这个蒟蒻，我调了一天，整整一天，

day1 晚上开始码 没有看题解 大约想了想，好像可以建反边跑lca

然后思考它有什么性质，首先题目里保证了只有一个出边，那么相当与保证了每个图都有一个环

想到可以缩点然后无脑lca 然后又想了想 好像环上比较难处理

day1 晚上码完 得了 38分 稍微改了改 28分

day2 重新理了理思路，想到环上可以预处理，但没想到怎么处理，随手打了个单调队列发现不行

得到了3分的好成绩

#include
#define ll long long
#define A 600000
using namespace std;
ll head[A],nxt[A],belong[A],ver[A],tot=0,deep[A],dis[A],t,n,m,dfn[A],sta[A],otp=0,num=0,top=0,low[A],f[A][30],cnt=0,ins[A],sum[A],rt[A],bl[A],zuzong[A],fa[A],bl4[A];
vector scc[251001];
bool flag[A];
void add(ll x,ll y)
{nxt[++tot]=head[x];ver[tot]=y;head[x]=tot;}
inline ll lca(ll x,ll y)
{
if(deep[x]>deep[y])swap(x,y);
for(ll i=t;i>=0;i--)
{
if(deep[x]==deep[y]) break;
if(deep[x]<=deep[f[y][i]]) y=f[y][i]; } if(x==y) return x; for(ll i=t;i>=0;i--)
if(f[x][i]!=f[y][i])
x=f[x][i],y=f[y][i];
return f[x][0];
}
void dfs(ll x,ll st,ll t)
{
deep[x]=st,flag[x]=1;bl4[x]=otp;
for(ll i=head[x];i;i=nxt[i])
{
ll y=ver[i];
if(flag[y]) continue;
rt[y]=t;
dis[y]=dis[x]+1;
f[y][0]=x;
dfs(y,st+1,t);
}
return ;
}
ll read()
{
ll f=1,x=0;char c=getchar();
while(!isdigit(c)){if(c=='-') f=-1;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
return f*x;
}
inline void tarjan(ll x)
{
dfn[x]=low[x]=++num;
sta[++top]=x;ins[x]=1;
for(ll i=head[x];i;i=nxt[i])
{
ll y=ver[i];
if(dfn[y]==0)
{
tarjan(y);
low[x]=min(low[x],low[y]);
}
else if(ins[y])
low[x]=min(low[x],dfn[y]);
}
if(dfn[x]==low[x])
{
++cnt;
ll yy=0,cis=0,lu;
while(1)
{
yy=sta[top--];
ins[yy]=0;
cis++;
bl4[yy]=cnt;
if(yy==x)
break;
scc[cnt].push_back(yy);
belong[yy]=-1;
//printf("将%lld赋成-1\n",yy);

    }  
    if(cis>1) scc\[cnt\].push\_back(x),belong\[x\]=-1;  
    else cnt--;  
}  

}
void tiaotarjan()
{
cout<<"***"<size)
{
ll j=ii-size;
if(!kais&&(scc[now][ii]==rt[xx]||scc[now][ii]==rt[yy]))
{
kais=1;
}
else if(kais==1)
{
de1<de2?de1++:de2++;
if(scc[now][ii]==rt[xx]||scc[now][ii]==rt[yy])
{
kais=0;
break;
}
}
}
else
{
if(!kais&&(scc[now][ii]==rt[xx]||scc[now][ii]==rt[yy]))
{
kais=1;
}
else if(kais==1)
{
de1<de2?de1++:de2++;
if(scc[now][ii]==rt[xx]||scc[now][ii]==rt[yy])
{
kais=0;
break;
}
}
}
}
printf("%lld %lld\n",de1,de2);
}
}
else
printf("-1 -1\n");
}
}
int main()
{work();}

和同学讨论这个题发现他们也挺艰难的

day2 下午 然后经过艰难的辨认+艰难的手膜得到以下代码

　　　　　　　　　 ll lx,ly,bl=belong[ances[x]],rootx=ances[x],rooty=ances[y],disx=deep[x]-deep[rootx],disy=deep[y]-deep[rooty],xy,yx;
for(ll j=0;jmax(disx,disy+yx)) printf("%lld %lld\n",disx,disy+yx);
else
{
if(min(disx+xy,disy)min(disx,disy+yx)) printf("%lld %lld\n",disx,disy+yx);
else if(disx+xy>=disy) printf("%lld %lld\n",disx+xy,disy);
else printf("%lld %lld\n",disx,disy+yx);
}

然后TLE了

得知tarjan一定会被卡死

然后改成了dfs（？？？？？？）

终于吧MLE整过了之后，就接着TLE

经过几个小时卡常斗争终于A了

#include
#define ll int
#define A 510000
const int L=1<<20|1; char buffer[L],*S,*T; #define getchar() ((S==T&&(T=(S=buffer)+fread(buffer,1,L,stdin),S==T))?EOF:*S++) using namespace std; ll head[A],nxt[A],belong[A],ver[A],tot=0,deep[A],t,n,m,otp=0,num=0,f[A][22],cnt=0,bl[A],ances[A],last,sz[A],v[A],cixu[A],chushi=0; inline ll find(ll x) {if(ances[x]==x) return x;return ances[x]=find(ances[x]);} inline void add(ll x,ll y) {nxt[++tot]=head[x];ver[tot]=y;head[x]=tot;} inline ll lca(ll x,ll y) { if(deep[x]>deep[y])swap(x,y);
ll w;
for(w=0;(1<=0;i--)
{
if(deep[x]==deep[y]) break;
if(deep[x]<=deep[f[y][i]]) y=f[y][i]; } if(x==y) return x; for(ll i=t;i>=0;i--)
if(f[x][i]!=f[y][i])
x=f[x][i],y=f[y][i];
return f[x][0];
}
inline void dfs(ll x,ll pre)
{
v[x]=++num;
deep[x]=deep[pre]+1;
// printf("%lld \n",deep[x]);
for(ll i=1;(1<last)
{
cnt++;
chushi=0;
cixu[x]=++chushi;
sz[cnt]++;
belong[x]=cnt;
ances[x]=x;
for(ll i=x;i!=y;i=f[i][0])
{
cixu[f[i][0]]=++chushi;
belong[f[i][0]]=cnt;
ances[f[i][0]]=f[i][0];
sz[cnt]++;
}
}
else
{
ances[y]=f[y][0]=x
,dfs(y,x);
}
}
}
inline ll Read(){
register ll ret;
register char r;
while(r=getchar(),r<'0'||r>'9');ret=r-48;
while(r=getchar(),r>='0'&&r<='9')ret=ret*10+r-48; return ret; } inline void work() { last=0; n=Read();m=Read(); t=log(n)/log(2)+1; for(ll i=1;i<=n;i++) { ll xx=Read(); add(xx,i); } for(ll i=1;i<=n;i++) if(!v[i]) { ances[i]=f[i][0]=i; dfs(i,0); last=num; } for(ll i=1;i<=m;i++) { ll x=Read(),y=Read(); if(find(x)!=find(y)&&belong[ances[x]]!=belong[ances[y]]) printf("-1 -1\n"); else { if(ances[x]==ances[y]) { ll lc=lca(x,y); printf("%d %d\n",deep[x]-deep[lc],deep[y]-deep[lc]); } else { ll lx,ly,bl=belong[ances[x]],disx=deep[x]-deep[ances[x]],disy=deep[y]-deep[ances[y]],xy,yx; lx=cixu[ances[x]];ly=cixu[ances[y]]; if(lxmax(disx,disy+yx)) printf("%d %d\n",disx,disy+yx);
else
{
if(min(disx+xy,disy)min(disx,disy+yx)) printf("%d %d\n",disx,disy+yx);
else if(disx+xy>=disy) printf("%d %d\n",disx+xy,disy);
else printf("%d %d\n",disx,disy+yx);
}
}
}
}
}
main()
{work();}

具体思路

首先我们会发现图中一定存在环而且仅仅存在一个环，可能有多个可分割的图，每个图都有一个环

我们要建反图，这样我们就可以跑lca了

然后我们模拟就完了，对于同一个图上的有如下情况

一.路径不经过环

lca完了

二.路径经过环

我们发现我们缩点时其实是按照一定顺序缩的，事实上是按照逆边顺序缩的

于是我们维护一个类似于dfn序的东西就完了

只在环上维护dfn序，相减就得到了距离

对于不在一个图上的直接-1 -1

#include
#define ll int
#define A 510000
const int L=1<<20|1; char buffer[L],*S,*T; #define getchar() ((S==T&&(T=(S=buffer)+fread(buffer,1,L,stdin),S==T))?EOF:*S++) using namespace std; ll head[A],nxt[A],belong[A],ver[A],tot=0,deep[A],t,n,m,otp=0,num=0,f[A][22],cnt=0,bl[A],ances[A],last,sz[A],v[A],cixu[A],chushi=0; inline ll find(ll x) {if(ances[x]==x) return x;return ances[x]=find(ances[x]);} inline void add(ll x,ll y) {nxt[++tot]=head[x];ver[tot]=y;head[x]=tot;} inline ll lca(ll x,ll y) { if(deep[x]>deep[y])swap(x,y);
ll w;
for(w=0;(1<=0;i--)
{
if(deep[x]==deep[y]) break;
if(deep[x]<=deep[f[y][i]]) y=f[y][i]; } if(x==y) return x; for(ll i=t;i>=0;i--)
if(f[x][i]!=f[y][i])
x=f[x][i],y=f[y][i];
return f[x][0];
}
inline void dfs(ll x,ll pre)
{
v[x]=++num;
deep[x]=deep[pre]+1;
// printf("%lld \n",deep[x]);
for(ll i=1;(1<last)
{
cnt++;
chushi=0;
cixu[x]=++chushi;
sz[cnt]++;
belong[x]=cnt;
ances[x]=x;
for(ll i=x;i!=y;i=f[i][0])
{
cixu[f[i][0]]=++chushi;
belong[f[i][0]]=cnt;
ances[f[i][0]]=f[i][0];
sz[cnt]++;
}
}
else
{
ances[y]=f[y][0]=x
,dfs(y,x);
}
}
}
inline ll Read(){
register ll ret;
register char r;
while(r=getchar(),r<'0'||r>'9');ret=r-48;
while(r=getchar(),r>='0'&&r<='9')ret=ret*10+r-48; return ret; } inline void work() { last=0; n=Read();m=Read(); t=log(n)/log(2)+1; for(ll i=1;i<=n;i++) { ll xx=Read(); add(xx,i); } for(ll i=1;i<=n;i++) if(!v[i]) { ances[i]=f[i][0]=i; dfs(i,0); last=num; } for(ll i=1;i<=m;i++) { ll x=Read(),y=Read(); if(find(x)!=find(y)&&belong[ances[x]]!=belong[ances[y]]) printf("-1 -1\n"); else { if(ances[x]==ances[y]) { ll lc=lca(x,y); printf("%d %d\n",deep[x]-deep[lc],deep[y]-deep[lc]); } else { ll lx,ly,bl=belong[ances[x]],disx=deep[x]-deep[ances[x]],disy=deep[y]-deep[ances[y]],xy,yx; lx=cixu[ances[x]];ly=cixu[ances[y]]; if(lxmax(disx,disy+yx)) printf("%d %d\n",disx,disy+yx);
else
{
if(min(disx+xy,disy)min(disx,disy+yx)) printf("%d %d\n",disx,disy+yx);
else if(disx+xy>=disy) printf("%d %d\n",disx+xy,disy);
else printf("%d %d\n",disx,disy+yx);
}
}
}
}
}
main()
{work();}