记录编号	120983	评测结果	AAAAAAAAAAAAAA
题目名称	[POI 2000] 管道迷宫	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.024 s
提交时间	2014-09-17 17:13:19	内存使用	0.53 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int SIZEN=6010;
const int HS=15049;
int N;
int col[SIZEN]={0};
int c[SIZEN][3]={0};
int f[SIZEN]={0};//hashֵ
int comp[SIZEN]={0};
int next[SIZEN]={0};
int head[HS]={0};
int ans;
bool check_same(int x,int y){
	if(col[x]!=col[y]) return false;
	for(int i=0;i<3;i++) if(comp[c[x][i]]!=comp[c[y][i]]) return false;
	return true;
}
void calc_hash(int x){
	for(int i=0;i<3;i++) f[x]=(f[x]*131)^f[c[x][i]];
	f[x]+=col[x],f[x]^=6423483;
	f[x]%=HS;
}
void insert(int pos,int x){
	next[x]=head[pos];
	head[pos]=x;
}
void work(void){
	for(int i=N-1;i>=1;i--){
		calc_hash(i);
		int x=head[f[i]];
		while(x){
			if(check_same(i,x)){
				ans--;
				comp[i]=x;
				goto NXT;
			}
			x=next[x];
		}
		insert(f[i],i);
		NXT:;
	}
	printf("%d\n",ans);
}
void read(void){
	cin>>N;
	char ch;
	for(int i=1;i<N;i++){
		cin>>ch;
		if(ch=='C') col[i]=1;
		else if(ch=='Z') col[i]=2;
		else if(ch=='N') col[i]=3;
		scanf("%d%d%d",&c[i][0],&c[i][1],&c[i][2]);
	}
	for(int i=1;i<=N;i++) comp[i]=i;
	ans=N;
}
int main(){
	freopen("lab.in","r",stdin);
	freopen("lab.out","w",stdout);
	read();
	work();
	return 0;
}