学步园

题目链接:http://poj.org/problem?id=2912

题目大意:

n个人(n<=500,编号0~n-1)玩石头剪刀布,其中一人是裁判,裁判也会参与.

除裁判外的n-1个人分组,相同组的人只会出一种手势,不同组的人出不同手势.

裁判可以任意出.

给出m局的结果,判断谁是裁判,如果知道谁是裁判,求出最早可判断的局号.

题目思路:

石头-->箭头-->布-->石头...食物链问题.

dis[i]=0:i 和 root 同组.

dis[i]=1:i 吃 root.

dis[i]=2:i 被 root 吃.

判断谁是裁判,用枚举即可.

如果枚举的是裁判的话,那么除了裁判参与的局,其余局势肯定是正常的.

之后就是逻辑分析了,看看什么情况"Impossible",什么情况"Can not determine"了.

代码:

#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <ctype.h>
#include <math.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
using namespace std;

#define ll long long
#define ls rt<<1
#define rs ls|1
#define lson l,mid,ls
#define rson mid+1,r,rs
#define middle (l+r)>>1
#define eps (1e-8)
#define type int
#define clr_all(x,c) memset(x,c,sizeof(x))
#define clr(x,c,n) memset(x,c,sizeof(x[0])*(n+1))
#define MOD 1000000009
#define INF 0x3f3f3f3f
#define pi acos(-1.0)
#define _max(x,y) (((x)>(y))? (x):(y))
#define _min(x,y) (((x)<(y))? (x):(y))
#define _abs(x) ((x)<0? (-(x)):(x))
#define getmin(x,y) (x= ((x)<0 || (y)<(x))? (y):(x))
#define getmax(x,y) (x= ((y)>(x))? (y):(x))
template <class T> void _swap(T &x,T &y){T t=x;x=y;y=t;}
int TS,cas=1;
const int M=500+5;
int n,m;
int fa[M],dis[M],wr[M<<2];

struct node{
	int a,b,c;
	void read(){
		char x;
		scanf("%d%c%d",&a,&x,&b);
		c= (x=='=')? 0:((x=='<')? 1:2);
	}
}p[M<<2];

int find(int x){
	int rt,i,j,sum=0;
	for(rt=x;rt!=fa[rt];rt=fa[rt]) sum+=dis[rt];
	for(i=x;i!=rt;i=j){
		sum-=dis[i];
		dis[i]=(dis[i]+sum)%3;
		j=fa[i];
		fa[i]=rt;
	}
	return rt;
}

void run(){
    int i,j;
	for(i=1;i<=m;i++) p[i].read();
	int cnt=0,res,resi,a,b,c;
	for(j=0;j<n;j++){
		wr[j]=0;
		for(i=0;i<n;i++) fa[i]=i,dis[i]=0;
		for(i=1;i<=m;i++){
			a=p[i].a,b=p[i].b,c=p[i].c;
			if(a==j || b==j) continue;
			int af=find(a),bf=find(b);
			if(af==bf && (dis[a]+c)%3!=dis[b]) break;
			if(af!=bf){
				fa[bf]=af;
				dis[bf]=(dis[a]-dis[b]+3+c)%3;
			}
		}
		if(i>m) cnt++,res=j;
		else wr[j]=i;
	}
	resi=0;
	for(i=0;i<n;i++) getmax(resi,wr[i]);
	if(cnt>1) puts("Can not determine");
	else if(!cnt) puts("Impossible");
	else printf("Player %d can be determined to be the judge after %d lines\n",res,resi);
}

void preSof(){
}

int main(){
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    preSof();
    //run();
    while(~scanf("%d%d",&n,&m)) run();
    //for(scanf("%d",&TS);cas<=TS;cas++) run();
    return 0;
}