萌新wa on #43,求助二分答案
查看原帖
萌新wa on #43,求助二分答案
1088663
zzzyyyyhhhhh楼主2024/7/25 11:57

我现在已经确定此节点在tmp到根的路径上,但二分答案出错。(real:1712 out:1709)

k_fa是获取k级祖先,res是答案

		int l=0,r=dep[tmp],mid,res=1;
		while(l<=r)
		{
			mid=(l+r)>>1;
			if(ask(k_fa(tmp,mid)))
			{
				res=k_fa(tmp,mid);
				r=mid-1;
			}
			else
			{
				res=k_fa(res,1);
				if(mid==dep[tmp]-1)
				{
					res=1;
					break;
				}
				r++;
				l=mid+2;
			}
		}
2024/7/25 11:57
加载中...