这题为啥我Maxn开55过不去啊
查看原帖
这题为啥我Maxn开55过不去啊
37409
Episode9楼主2020/5/20 10:38

嗯哼哼WA on#2 #4一直输出1(个)1(个)1(个)啊啊啊啊啊啊 Maxn开105就过了。

#include<bits/stdc++.h>
#define Maxn 105
using namespace std;
int size[Maxn],N,M,head[Maxn],hash[Maxn],ans[Maxn],prime[Maxn],p[Maxn],tot=0,cnt=0;
bool is_prime[Maxn];
struct edge{int next,to;}e[Maxn<<1];
inline void add(int x,int y)
{
	e[++cnt].next=head[x];
	e[cnt].to=y;
	head[x]=cnt;
}
inline void get_size(int now,int fa)
{
	size[now]=1;
	for (int i=head[now];i;i=e[i].next)
	{
		int v=e[i].to;
		if (v==fa) continue;
		get_size(v,now);
		size[now]+=size[v]; 
	}
}
inline void get_hash(int now,int fa)
{
	hash[now]=size[now]*prime[size[now]]%19260817;
	for (int i=head[now];i;i=e[i].next)
	{
		int v=e[i].to;
		if (v==fa) continue;
		get_hash(v,now);
		hash[now]+=hash[v];
		hash[now]%=19260817;
	}
}
int main()
{
	for (int i=2;i<=Maxn-5;i++)
	{
		if (!is_prime[i]) prime[++tot]=i;
		for (int j=1;j<=tot&&i*prime[j]<=Maxn-5;j++)
		{
			is_prime[i*prime[j]]=1;
			if (i%prime[j]==0) break;
		}
	}
	scanf("%d",&M);
	for (int i=1;i<=M;i++)
	{
		
		memset(head,0,sizeof(head));
		memset(e,0,sizeof(e));
		cnt=0;
		scanf("%d",&N);
		for (int x,j=1;j<=N;j++) 
		{
			scanf("%d",&x);
			if (x==0) continue;
			add(x,j),add(j,x);
		}
		for (int rt=1;rt<=N;rt++)
		{
			memset(size,0,sizeof(size));
			memset(hash,0,sizeof(hash));
			get_size(rt,0);
			get_hash(rt,0);
			p[rt]=hash[rt];
		}
		sort(p+1,p+N+1);
		for (int j=1;j<=N;j++) ans[i]+=p[j]*prime[j]%19260817,ans[i]%=19260817;
	}
	for (int i=1;i<=M;i++)
	for (int j=1;j<=i;j++)
	if (ans[i]==ans[j]) {cout<<j<<endl;break;}
	return 0;
}
2020/5/20 10:38
加载中...