fnoichzhe 2017-12-30 06:34:44
点我顶贴
收藏
删除
#include<cstdio>
const int N=55000;
int ans,n,k,d,x,y,px,py,x1,y1,d1,f[N],p[N];
int get1(int x,int &px){
//计算x的树根并计算x到树根的和,结果存入px
if(!f[x]) return x;
else {px=(px+p[x])%3;return get1(f[x],px);}
}
int main(){
freopen("poj1182.in","r",stdin);
freopen("poj1182.out","w",stdout);
//读入数据并处理
scanf("%d%d",&n,&k);
ans=0;
//初始化
for(int i=1;i<=n;i++) f[i]=0;
for(int i=1;i<=k;i++){
scanf("%d%d%d",&d,&x,&y);
if(x>n||y>n) {ans++;continue;}
if(d==2&&x==y) {ans++;continue;}
//处理d x y
d--;px=0;py=0;
//计算x的树根x1,同时计算px,表示x到树根距离%3
x1=get1(x,px);
//计算y的树根y1,同时计算py,表示y到树根距离%3
y1=get1(y,py);
if(x1!=y1){
//连接树根
f[x1]=y1;
d1=(py-d+3)%3;
p[x1]=(d1-px+3)%3;
}
else{
//计算x和y的关系d1
d1=(py-px+3)%3;
if(d!=d1) ans++;
}
}
printf("%d",ans);
return 0;
}