Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
求教各位高手指点迷津,我的代码(有注释)总是wa,给点测试数据也行啊#include <stdio.h> #define MAX 50010 int parent[MAX]; int relation[MAX]; // 若为 1,表示吃parent; 若为 2,表示被parent吃; 若为 0,表示与跟同类 int find(int nod) // 返回nod所在的树的根节点 { int p = parent[nod]; if(p<0) return nod; // nod 是根节点 while(parent[p]>0) p = parent[p]; return p; } int relat_root(int nod) //返回一个节点与其根与根的关系 { int p, res=0; p = parent[nod]; res += relation[nod]; while(p>0) { res += relation[p]; p = parent[p]; } res = res % 3; return res; } int relat(int a, int b) //返回俩个节点的关系 { int rel_a, rel_b; // 分别存放 a, b 与根的关系 rel_a = relat_root(a); rel_b = relat_root(b); int relat_ab; if(rel_a == rel_b) relat_ab = 0; else if(rel_a-rel_b==1 || rel_a-rel_b==-2) relat_ab = 1; else relat_ab = 2; return relat_ab; } void merge(int rx, int ry, int rel_x, int rel_y, int d) // 归并rx和ry两棵树 { if(parent[rx]>=parent[ry]) //树rx的节点数比较少,让rx指向ry { parent[ry] += parent[rx]; parent[rx] = ry; if(d==1) { if(rel_x==rel_y) relation[rx] = 0; else if(rel_x-ry==-1 || rel_x-ry==2) relation[rx] = 1; else relation[rx] = 2; } else // d==2 { if(rel_x==rel_y) relation[rx] = 1; else if(rel_x-rel_y==-2 || rel_x-rel_y==1) relation[rx] = 0; else relation[rx] = 2; } } if(parent[rx]<parent[ry]) //树ry的节点数比较少,让ry指向rx { parent[rx] += parent[ry]; parent[ry] = rx; if(d==1) { if(rel_x==rel_y) relation[ry] = 0; else if(rel_x-rel_y==-1 || rel_x-rel_y==2) relation[ry] = 2; else relation[ry] = 1; } else // d==2 { if(rel_x==rel_y) relation[ry] = 2; else if(rel_x-rel_y==-2 || rel_x-rel_y==1) relation[ry] = 0; else relation[ry] = 1; } } } int main() { int n, d; int k, x, y; int i, cnt=0; scanf("%d%d", &n, &k); for(i=1;i<=n;i++) { parent[i] = -1; relation[i] = 0; }// initialization for(i=1; i<=k; i++) { scanf("%d%d%d", &d, &x, &y); if( x>n||y>n ) { cnt++; /*printf("LIE: invalid input! i=%d : cnt=%d\n", i, cnt);*/ continue; } int rx, ry; rx = find(x); // printf("root of x:%d ", rx); ry = find(y); // printf("root of y:%d\n", ry); if(rx==ry ) { if(relat(x, y) != d-1) { cnt++; /* printf("LIE:i=%d : cnt=%d\n", i, cnt); */} } else if(rx!=ry) { int rel_x, rel_y; rel_x = relat_root(x); rel_y = relat_root(y); merge(rx, ry, rel_x, rel_y, d); } } printf("%d", cnt); return 0; } Followed by:
Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator