Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

为什么你们 全是一种做法,说下我的做法大神给看看错在哪~

Posted by 2015327100024 at 2016-07-24 18:27:47 on Problem 2912 and last updated at 2016-07-24 19:23:51
大多数做法都是枚举从(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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator