获得了50分的好成绩,求助!
查看原帖
获得了50分的好成绩,求助!
261262
WaltVBAlston楼主2020/11/1 13:16

第二个点就错了,报错信息:

Wrong Answer. wrong answer On line 24153 column 1, read 4, expected 2.

好像问题不是很大,但是有点麻烦,谁有类似经历吗?或者哪位数据结构大佬能帮我看一下代码?谢谢!

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
int n,q,s,m;
int u[1000005],v[1000005],before[1000005],now[1000005],fa[500005][20],depth[500005];
int max_log=0;
void dfs(int x,int fath){
	fa[x][0]=fath;
	depth[x]=depth[fath]+1;
	for(int i=1;i<=max_log;i++){
		fa[x][i]=fa[fa[x][i-1]][i-1];
	}
	for(int i=now[x];i!=-1;i=before[i]){
		if(v[i]!=fath)
			dfs(v[i],x);
	}
	return;
}
int lca(int a,int b){
	if(depth[a]<depth[b])
		swap(a,b);
	for(int i=max_log;i>=0;i--)
		if(depth[fa[a][i]]>=depth[b])
			a=fa[a][i];
	if(a==b)
		return a;
	for(int i=max_log;i>=0;i--){
		if(fa[a][i]!=fa[b][i]){
			a=fa[a][i];
			b=fa[b][i];
		}
	}
	return fa[a][0];
}
int main(){
	cin>>n>>q>>s;
	m=n-1;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=20;j++)
            fa[i][j]=i;
	memset(now,-1,sizeof(now));
	for(int i=1;i<=m;i++){
		cin>>u[i]>>v[i];
		before[i]=now[u[i]];
		now[u[i]]=i;
	}
	for(int i=m;i<=2*m;i++){
		u[i]=v[i-m];
		v[i]=u[i-m];
		before[i]=now[u[i]];
		now[u[i]]=i;
	}
	depth[s]=1;
	while(pow(2,max_log)<n)
		max_log++;
	dfs(s,s);
	while(q--){
		int a,b;
		cin>>a>>b;
		cout<<lca(a,b)<<endl;
	}
	return 0;
}
2020/11/1 13:16
加载中...