食物链题解

ilibilib / 2024-06-08 / 原文

由题得，所有动物整体关系如上。

起初每个动物相互时间没有关系，bb[i]=i。

对于 x 与 y：

如果它们是同类即 x 到 y 的距离为 $0$，或者转了几圈，一圈距离为 $3$，即模 $3$ 余 $0$。

如果 x 捕食 y，就是 x 到 y 距离模 $3$ 余 $1$。

对 x 与 y 操作时：

如果它们没有关系(它们不被之前给出的某个条件边联通)

对于操作 1 x y ，就是在 x 与 y 之间连上边权为 $0$ 的边。

对于操作 2 x y ，就是在 x 与 y 之间连上边权为 $1$ 的边。

如果它们有关系(即存在关系边将它们联通了)

判断 x 到 y 的距离是否符合给出的条件。

可以用带权并查集维护。

code：

#include<bits/stdc++.h>
#define N 100010
using namespace std;
int bb[N],dp[N];
int zbb(int x)
{
	if(bb[x]==x)return x;
	int p=zbb(bb[x]);
	dp[x]=(((dp[x]+dp[bb[x]])%3)+3)%3;
	return bb[x]=p;
}
void hb(int x,int y,int c)
{
	int bx=zbb(x),by=zbb(y);
	if(bx==by) return;
	bb[bx]=by,dp[bx]=(((dp[y]+c-dp[x])%3)+3)%3;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int ans=0,n,k,op,x,y;cin>>n>>k;
	for(int i=1;i<=n;++i) bb[i]=i;
	while(k--)
	{
		cin>>op>>x>>y;
		if(x>n||y>n) {++ans;continue;};
		if(x==y&&op==2) {++ans;continue;};
		if(x==y) continue;
		if(zbb(x)==zbb(y))
		{
			if(op==1&&((dp[x]%3)+3)%3!=((dp[y]%3)+3)%3) {++ans;continue;};
			if(op==2&&((dp[x]-dp[y]%3)+3)%3!=1) {++ans;continue;};
		}
		else
		{
			if(op==1) hb(x,y,0);
			if(op==2) hb(x,y,1);
		}
	}
	cout<<ans;	
}