社区讨论
为什么数组开大就过了,想不明白
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 条回复,欢迎继续交流。
正在加载回复...