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 |
为什么你们 全是一种做法,说下我的做法大神给看看错在哪~大多数做法都是枚举从(i = 1~N),假设当前的i为裁判,忽略和i相同的,如果只有一个 i没有漏洞,就说明i是裁判。 我的做法是直接并查集输入数据(i = 1~m)的时候检测漏洞,如果检查到有两个漏洞,并且两个漏洞里出现了同一个人,就说明那个人为备选裁判,再重新枚举一次检查以此人为裁判是否符合题意,最后输出。 或者帮我指出有什么冲突的数据也行,非常感谢! #include<cstdio> #include<iostream> #include<algorithm> #include<cstring> using namespace std; const int maxn = 5005; int father[maxn],Rank[maxn],n,m; struct Edge { int x,y; char c; } edge[20005]; int query(int x) { if(x != father[x]) { int per = father[x]; father[x] = query(father[x]); Rank[x] = (Rank[x] + Rank[per] + 3) % 3; } return father[x]; } int main() { //freopen("hah.txt","r",stdin); while(~scanf("%d%d",&n,&m)) { for(int i = 0;i <= n;i++) { Rank[i] = 0; father[i] = i; } int x,y,ans = -1,ch,ni,cnt = 0,k,flag = 1; char c; for(int i = 0;i < m;i++) { scanf("%d%c%d",&edge[i].x,&edge[i].c,&edge[i].y); x = edge[i].x; y = edge[i].y; c = edge[i].c; if(c == '<') swap(x,y); int a = query(x); int b = query(y); if(a == b && flag && cnt < 2) { if((Rank[y] - Rank[x] + 3) % 3 != 0 && c == '=') cnt++; else if(c != '=' && (Rank[y] - Rank[x] + 3) % 3 != 1 && (Rank[y] - Rank[x] + 3) % 3 != -2) cnt++; if(cnt == 1) { ch = x; ni = y; } else if((ch == x && ni == y) || (ch == y && ni == x)) { cnt--; continue; } //printf("%d-%d %d\n",x,y,cnt); if(cnt == 2) { if(ch == x || ch == y) { k = i; ans = ch; } else if(ni == x || ni == y) { k = i; ans = ni; } else flag = 0; } } if(a != b && flag && cnt < 2) { father[b] = a; if(c == '=') Rank[b] = (Rank[x] - Rank[y] + 3) % 3; else Rank[b] = (Rank[x] - Rank[y] + 4) % 3; } } for(int i = 0; i <= n;i++) { Rank[i] = 0; father[i] = i; } if(ans != -1) { for(int i = 0;i < m;i++) { if(edge[i].x == ans || edge[i].y == ans) continue; int xx = edge[i].x; int yy = edge[i].y; if(edge[i].c == '<') swap(xx,yy); int a = query(xx); int b = query(yy); char cc = edge[i].c; //printf("%d %d-%d\n",ans,a,b); if(a == b) { if((Rank[yy] - Rank[xx] + 3 ) % 3 != 0 && cc == '=') { flag = 0; break; } if(cc != '=' && (Rank[yy] - Rank[xx] + 3) % 3 != 1 && (Rank[yy] - Rank[xx] + 3) % 3 != -2) { flag = 0; break; } } else { father[b] = a; if(cc == '=') Rank[b] = (Rank[xx] - Rank[yy] + 3) % 3; else Rank[b] = (Rank[xx] - Rank[yy] + 4) % 3; } } } /*for(int i = 0;i < n;i++) printf("%d-",Rank[i]); printf("\n");*/ if(n == 1 && flag) { if(cnt == 0) printf("Player 0 can be determined to be the judge after 0 lines\n"); else printf("Impossible\n"); } else { if(!flag) printf("Impossible\n"); else if(ans != -1 && flag && cnt > 1) printf("Player %d can be determined to be the judge after %d lines\n",ans,k+1); else printf("Can not determine\n"); } } } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator