社区讨论

为什么数组开大就过了,想不明白

P5043【模板】树同构 / [BJOI2015] 树的同构参与者 3已保存回复 3

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
3 条
当前快照
1 份
快照标识符
@lo2azil3
此快照首次捕获于
2023/10/23 10:53
2 年前
此快照最后确认于
2023/11/03 11:04
2 年前
查看原帖
CPP
#include<bits/stdc++.h>
#define ll long long 
using namespace std;
int edgenum,n;
int vet[5000],nxt[5000],head[1000],siz[1000];
const ll mod=1e9+7,base=233;
ll H[1000][1000];
void add(int u,int v)
{
	vet[++edgenum]=v;
	nxt[edgenum]=head[u];
	head[u]=edgenum;
}
ll get_hash(int u,int f)
{
	vector<ll> vec;
	siz[u]=1;
	for (int e=head[u];e;e=nxt[e])
	{
		int v=vet[e];
		if (v==f) continue;
		vec.push_back(get_hash(v,u));
		siz[u]+=siz[v];
	}
	if (siz[u]==1) return 1;
	sort(vec.begin(),vec.end());
	ll sum=0;
	for (int i=0;i<vec.size();i++)
		sum=(sum*base+vec[i])%mod;
	return sum*siz[u];
}
int main()
{
	int m,i,j,x,y;
	scanf("%d",&m);
	for (i=1;i<=m;i++)
	{
		memset(head,0,sizeof(head));
		scanf("%d",&n);
		for (j=1;j<=n;j++)
		{
			scanf("%d",&x);
			if (x!=0) add(j,x),add(x,j);
		}
		for (j=1;j<=n;j++) H[i][j]=get_hash(j,0);
		for (j=1;j<=m;j++)
		  for (x=1;x<=n;x++)
		    for (y=1;y<=n;y++)
		      if (H[i][x]==H[j][y])
		      {
		      	printf("%d\n",j);
		      	goto GG;
			  }
		GG:
			continue;
	}
	return 0;
}
CPP
#include<bits/stdc++.h>
#define ll long long 
using namespace std;
int edgenum,n;
int vet[500],nxt[500],head[100],siz[100];
const ll mod=1e9+7,base=233;
ll H[100][100];
void add(int u,int v)
{
	vet[++edgenum]=v;
	nxt[edgenum]=head[u];
	head[u]=edgenum;
}
ll get_hash(int u,int f)
{
	vector<ll> vec;
	siz[u]=1;
	for (int e=head[u];e;e=nxt[e])
	{
		int v=vet[e];
		if (v==f) continue;
		vec.push_back(get_hash(v,u));
		siz[u]+=siz[v];
	}
	if (siz[u]==1) return 1;
	sort(vec.begin(),vec.end());
	ll sum=0;
	for (int i=0;i<vec.size();i++)
		sum=(sum*base+vec[i])%mod;
	return sum*siz[u];
}
int main()
{
	int m,i,j,x,y;
	scanf("%d",&m);
	for (i=1;i<=m;i++)
	{
		memset(head,0,sizeof(head));
		scanf("%d",&n);
		for (j=1;j<=n;j++)
		{
			scanf("%d",&x);
			if (x!=0) add(j,x),add(x,j);
		}
		for (j=1;j<=n;j++) H[i][j]=get_hash(j,0);
		for (j=1;j<=m;j++)
		  for (x=1;x<=n;x++)
		    for (y=1;y<=n;y++)
		      if (H[i][x]==H[j][y])
		      {
		      	printf("%d\n",j);
		      	goto GG;
			  }
		GG:
			continue;
	}
	return 0;
}
上面的代码是AC,下面的只有30分,区别只有数组范围。。。

回复

3 条回复,欢迎继续交流。

正在加载回复...