为什么第 $5$ 个点WA?
查看原帖
为什么第 $5$ 个点WA?
488734
wrzSama楼主2022/11/5 13:46

为什么把超级源点设成 0055 个点会 WA,而设成 n+1n+1 就 AC 了?

#include<bits/stdc++.h>
#define re register
#define ll long long
using namespace std;
inline int read()
{
	int res=0;
	bool op=0;
	char ch=getchar();
	while(!isdigit(ch))
	{
		op|=ch=='-';
		ch=getchar();
	}
	while(isdigit(ch))
	{
		res=(res<<3)+(res<<1)+(ch^48);
		ch=getchar();
	}
	return op?-res:res;
}
inline void write(int x)
{
	if(x<0)
	{
		putchar('-');
		x=-x;
	}
	if(x>9) write(x/10);
	putchar(x%10^48);
}
int n,in[65540],out[65440],d[65440],fa[65440][18],ans[65440];
vector<int>s1[65540],s2[65440];
inline int lca(int x,int y)
{
	if(d[x]<d[y]) swap(x,y);
	for(re int i=17;~i;--i) if((d[x]-d[y])>>i&1) x=fa[x][i];
	if(x==y) return x;
	for(re int i=17;~i;--i)
	{
		if(fa[x][i]!=fa[y][i])
		{
			x=fa[x][i];
			y=fa[y][i];
		}
	}
	return fa[x][0];
}
int main()
{
	n=read();
	for(re int i=1;i<=n;++i)
	{
		int x=read();
		while(x)
		{
			s1[x].push_back(i);
			s2[i].push_back(x);
			++in[i];
			++out[x];
			x=read();
		}
	}
	queue<int>q;
	for(re int i=1;i<=n;++i) if(!in[i]) q.push(i);
	while(q.size())
	{
		int u=q.front(),x=0;
		q.pop();
		for(re int i=0;i<s2[u].size();++i)
		{
			int v=s2[u][i];
			if(!x) x=v;
			else x=lca(x,v);
		}
		if(!x) x=n+1;//一开始是 $0$
		fa[u][0]=x;
		d[u]=d[x]+1;
		for(re int i=1;i<18;++i) fa[u][i]=fa[fa[u][i-1]][i-1];
		for(re int i=0;i<s1[u].size();++i)
		{
			int v=s1[u][i];
			--in[v];
			if(!in[v]) q.push(v);
		}
	}
	for(re int i=1;i<=n;++i)
	{
		if(!out[i]) q.push(i);
		ans[i]=1;
	}
	while(q.size())
	{
		int u=q.front();
		q.pop();
		ans[fa[u][0]]+=ans[u];
		for(re int i=0;i<s2[u].size();++i)
		{
			int v=s2[u][i];
			--out[v];
			if(!out[v]) q.push(v);
		}
	}
	for(re int i=1;i<=n;++i)
	{
		write(ans[i]-1);
		puts("");
	}
	return 0;
}
2022/11/5 13:46
加载中...