讨论 / OMFG-ACBOOLG 题解
fnoichzhe 2017-12-30 22: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;

}

查看更多回复
提交回复