只错一个点的WA……问问什么情况
查看原帖
只错一个点的WA……问问什么情况
441366
dingyichen楼主2024/4/15 20:05
#include<bits/stdc++.h>//2024-4-8
using namespace std;//2024-4-10
struct edge//2024-4-12
{
	int v,next;//2024-4-15
	bool vis;
}e[300030];
int h[100010],q=1;
void add(int x,int y)
{
	q++;
	e[q].v=y;
	e[q].next=h[x];
	h[x]=q;
}
int n,m;
bool vis[100010],instack[100020];
int stk[200020],low[100010],dfn[100010],num[100010],f[100010][25],cnt,dft,top;
int depth[100010];
int f2[100010][25];
void doit(int x)
{
	dfn[x]=++dft;
	stk[++top]=x;
	vis[x]=instack[x]=1;
	low[x]=dfn[x];
	int next=h[x];
	while(next)
	{
		if(e[next].vis==0)
		{
			e[next].vis=e[next^1].vis=1;
			if(vis[e[next].v]&&instack[e[next].v])
			{
				low[x]=min(low[x],dfn[e[next].v]);
			}
			else if(!vis[e[next].v])
			{
				doit(e[next].v);
				if(low[e[next].v]>=dfn[x])
				{
					while(stk[top+1]!=e[next].v)
					{
						instack[stk[top]]=0;
						num[stk[top]]=e[next].v;
						top--;
					}
					f2[e[next].v][0]=f[e[next].v][0]=x;
				}
				low[x]=min(low[x],low[e[next].v]);
			}
		}
		next=e[next].next;
	}
	return ;
}
void get_depth(int x)
{
	x=num[x];
	if(depth[x])return;
	if(f[x][0]==0)depth[x]=1;
	else
	{
		get_depth(f[x][0]);
		depth[x]=depth[f[x][0]]+1;
	}
	return;
}
int todepth(int x,int d)
{
	
	int t=depth[x]-d;
	if(!t)return x;
	if(t<0)
	{
		return -1;
	}
	int y=log2(t);
	return todepth(f[x][y],d);
}
int todepth2(int x,int d)
{
	int t=depth[num[x]]-d;
	if(!t)return x;
	if(t<0)
	{
		return -1;
	}
	int y=log2(t);
	return todepth2(f2[num[x]][y],d);
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int t1,t2;
		scanf("%d%d",&t1,&t2);
		add(t1,t2);
		add(t2,t1);
	}
	doit(1);
	num[1]=1;
	for(int i=1;i<=n;i++)
	{
		f[i][0]=num[f[i][0]];
	}
	for(int i=1;i<=n;i++)
	{
		get_depth(i);
	}
	for(int i=1;1<<i<n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			f[j][i]=f[f[j][i-1]][i-1];
			f2[j][i]=f2[num[f2[j][i-1]]][i-1];
		}
	}
	int q;
	cin>>q;
	for(int i=1;i<=q;i++)
	{
		int t1,t2,t3,t4;
		scanf("%d%d%d",&t1,&t2,&t3);
		/*if(i==1&&t1==45)
		{
			cout<<"no\n";
			continue;
		}*/
		t1=num[t1];t2=num[t2];t4=t3;t3=num[t3];
		int t1f=todepth2(t1,depth[t3]),t2f=todepth2(t2,depth[t3]),t1check=todepth(t1,depth[t3]+1),t2check=todepth(t2,depth[t3]+1);
		if((t1f==t4||t2f==t4)&&(t1check!=t2check))
		{
			printf("yes\n");
		}
		else
		{
			printf("no\n");
		}
	}
return 0;
}

只有第一个测试点的第一个数据错。。。

2024/4/15 20:05
加载中...