WA90pts求助
查看原帖
WA90pts求助
244039
KDZ22楼主2023/7/29 11:04
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const int MAXX=57;
int m,n;
ull Hash_1[MAXX],Hash_2[MAXX];
ull mask,Mod;
vector<int>g[MAXX][MAXX];
ull shift(ull x){
	x^=mask;
	x^=x<<7;
	x^=x>>13;
	x^=x<<17;
	x^=mask;
	return x;
}
ull dfs(int id,int u,int fa){
	ull temp=1;
	for(int i=0;i<(int)g[id][u].size();i++){
		if(g[id][u][i]==fa) continue;
		temp+=shift(dfs(id,g[id][u][i],u))%Mod;
		temp%=Mod;
	}
	return temp;
}
int main(){
	srand(time(0));
	mask=rand();
	Mod=shift(rand());
	scanf("%d",&m);
	for(int i=1;i<=m;i++){
		scanf("%d",&n);
		int v;
		for(int j=1;j<=n;j++){
			scanf("%d",&v);
			if(!v) continue;
			g[i][j].push_back(v);
			g[i][v].push_back(j);
		}
	}
	for(int i=1;i<=m;i++){
		for(int j=1;j<=n;j++){
			ull w=dfs(i,j,0);
			Hash_1[i]+=w*w%Mod;
			Hash_2[i]+=((w*w)%Mod*w)%Mod;
		}
	}
	for(int j=1;j<=m;j++){
		for(int k=1;k<=m;k++){
			if(Hash_1[j]==Hash_1[k]&&Hash_2[j]==Hash_2[k]){
				printf("%d\n",k);
				break;
			}
		}
	}
	return 0;
}

卡7#点过不了

2023/7/29 11:04
加载中...