比赛 20120809 评测结果 AAAAAAAAAA
题目名称 食物中毒 最终得分 100
用户昵称 Makazeu 运行时间 0.160 s
代码语言 C++ 内存使用 0.31 MiB
提交时间 2012-08-09 09:53:51
显示代码纯文本
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
using namespace std;
typedef long long LL;
const string able="Possible";
const string unable="Impossible";
LL med[21]={0LL},goal=0LL;
int N,M,n;
LL now,x,ichi=1LL;

inline void init()
{
	goal=0;
	for(int i=1;i<=M;i++)
	{
		scanf("%lld",&x);
		goal=goal+((ichi)<<(x-ichi));
	}
	for(int i=1;i<=N;i++)
	{
		med[i]=0LL;
		scanf("%d",&n);
		for(int j=1;j<=n;j++)
		{
			scanf("%lld",&x);
			med[i]=med[i] ^ ((ichi)<<(x-ichi));
		}
	}
	now=0LL;
}

bool dfs(int deep)
{
	if(deep==N+1)
	{
		if((now&goal)==goal)
			return true;
		return false;
	}
	LL tmp=now;
	now^=med[deep];
	if(dfs(deep+1))  return true;
	now=tmp; 
	if(dfs(deep+1)) return true;
	return false;
}

int main()
{
	freopen("medicine.in","r",stdin);
	freopen("medicine.out","w",stdout);
	while(scanf("%d %d\n",&N,&M)==2)
	{
		init();
		if(dfs(1)) printf("%s\n",able.c_str());
		else printf("%s\n",unable.c_str());
	}
	return 0;
}