| ||||||||||
| 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