【POJ 2425】A Chess Game

题目传送门：http://poj.org/problem?id=2425

这个题目，第一眼想到肯定是状压SG，然后发现MLE+TLE
于是发现棋子之间互不影响，于是等价为NIM
证明不会QAQ，不过贾志豪的论文里讲：这是性质QAQ

MD之前看的中文体面有问题，浪费了两个小时
以后还是乖乖看原题面吧！

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

const int MAXN = 1000+9;

int n,head[MAXN],T,nxt[MAXN*MAXN],to[MAXN*MAXN],m,f[MAXN],vout,dig[MAXN],tot;

inline int read(){
	char c=getchar(); int ret=0;
	while (c<'0'||c>'9') c=getchar();
	while (c<='9'&&c>='0') ret=ret*10+c-'0',c=getchar();
	return ret;
}

inline void AddEdge(int u, int v){
	to[++T] = v; nxt[T] = head[u]; head[u] = T;
}

int Get(int w){
	if (!~f[w]) { 
		int tmp = ++tot;
		for (int i=head[w];i;i=nxt[i]) Get(to[i]);
		for (int i=head[w];i;i=nxt[i]) dig[f[to[i]]] = tmp;
		for (int i=0;i<MAXN;i++) if (dig[i] != tmp) {f[w] = i; break;}
	} return f[w];
}

int main(){
	while (~scanf("%d",&n)) {
		T = 0; memset(head,0,sizeof(head)); memset(f,-1,sizeof(f));
		for (int i=1,tmp;i<=n;i++) {
			tmp = read(); 
			if (!tmp) f[i] = 0;
			else for (int j=tmp;j;j--) AddEdge(i,read()+1);
		}
		while (m = read()) { vout = 0;
			for (int i=1;i<=m;i++) vout ^= Get(read()+1); 
			if (!vout) printf("LOSE\n");
			else printf("WIN\n");
		} 
	}
	return 0;
}