错误的 lca 得90pts
查看原帖
错误的 lca 得90pts
465032
Last_Flame楼主2023/12/13 16:46

我写的求lca代码犯了一个智障错误,但是依然有90分,其中#7RE。

我使用倍增求lca,具体的,我在让深度较大的点跳到较小深度的时候,判断条件写成了“深度大于另一个点的编号”,但是依然能过90分,是因为数据太水还是这样求出来的lca具有类似作用?

int getlca(int p1,int p2){
	int pt=0;
	if(dep[p1]<dep[p2]) swap(p1,p2);
	while(dep[p1]>dep[p2]){
		pt=0;
		while(dep[fa[p1][pt+1]]>=p2) pt++;	//这个位置,p2应该改为dep[p2]
		p1=fa[p1][pt];
	}
	while(p1!=p2){
		pt=0;
		while(fa[p1][pt+1]!=fa[p2][pt+1]) pt++;
		p1=fa[p1][pt],p2=fa[p2][pt];
	}
	return p1;
}
2023/12/13 16:46
加载中...