记录编号	387838	评测结果	AAAAAAAAAA
题目名称	[HZOI 2016]MC之旅：逃离基友	最终得分	100
用户昵称	yourfather	是否通过	通过
代码语言	C++	运行时间	0.207 s
提交时间	2017-03-27 17:58:25	内存使用	3.70 MiB

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn = 41000;
const int maxm = 100100;
struct Link{int to,next;}link[maxm*4];
int head[maxn]={0},tot = 0,sta[maxn],c = 0;
bool mark[maxn]={0};
int N,M;
 
void add(int from,int to){
	link[++tot].to = to;
	link[tot].next = head[from];
	head[from] = tot;
}
bool dfs(int x){
	if(mark[x^1])return false;
	if(mark[x])return true;
	sta[++c] = x;
	mark[x] = true;
	for(int i = head[x];i;i=link[i].next)
		if(!dfs(link[i].to))return false;
	return true;
}
bool running(){
	for(int i = 0;i < 2*N;i+=2){
		if(!mark[i]&&!mark[i^1]){
			c = 0;
			if(!dfs(i)){
				while(c > 0)mark[sta[c--]] = false;
				if(!dfs(i^1))return false;
			}
		}
	}
	return true;
}
int main(){
	freopen("T3_.in","r",stdin);
	freopen("T3_.out","w",stdout);
	while(scanf("%d%d",&N,&M)!=EOF){
		memset(mark,0,sizeof(mark));
		c = 0;tot = 0;memset(head,0,sizeof(head));
		N<<=1;int opt,a,b;
		for(int i = 1;i <= M;i++){
			scanf("%d",&opt);
			switch(opt){
				case 1:// i == true
					scanf("%d",&a);a--;
					add(a^1,a);
					break;
				case 2:// i == false
					scanf("%d",&a);a--;
					add(a,a^1);
					break;
				case 3:// i and j == true
					scanf("%d%d",&a,&b);a--;b--;
					add(a^1,a);
					add(b^1,b);
					break;
				case 4:// i and (!j) == true -> i = true,j = false
					scanf("%d%d",&a,&b);a--;b--;
					add(a^1,a);
					add(b,b^1);
					break;
				case 5: //i or j == true;
					scanf("%d%d",&a,&b);a--;b--;
					add(a^1,b);
					add(b^1,a);
					break;
				case 6:// i or (not j) ->1 1 || 1 0 || 0 0
					scanf("%d%d",&a,&b);a--;b--;
					add(a^1,b^1);
					add(b,a);
					break;
				case 7:// not (i and j) -> 1 0||0 1||0 0
					scanf("%d%d",&a,&b);a--;b--;
					add(a,b^1);
					add(b,a^1);
					break;
				case 8://not (i or j) -> 0 0;
					scanf("%d%d",&a,&b);a--;b--;
					add(a,a^1);
					add(b,b^1);
					break;
				case 9://i xor j -> i!=j
					scanf("%d%d",&a,&b);a--;b--;
					add(a^1,b);
					add(a,b^1);
					add(b^1,a);
					add(b,a^1);
					break;
				case 10://not (i xor j)->(i xor j)=false->i == j
					scanf("%d%d",&a,&b);a--;b--;
					add(a,b);
					add(b,a);
					add(a^1,b^1);
					add(b^1,a^1);
					break;
				case 11://i xor (not j)->0 0 1 1 i = j
					scanf("%d%d",&a,&b);a--;b--;
					add(a,b);
					add(a^1,b^1);
					add(b^1,a^1);
					add(b,a);
					break;
				case 12://(!i) or (!j) 0 0 || 0 1 || 1 0
					scanf("%d%d",&a,&b);a--;b--;
					add(a,b^1);
					add(b,a^1);
					break;
			}
		}
		if(!running()){puts("die");}
		else {
			for(int i = 0;i < N;i++){
				if(mark[i])printf("%d ",i+1);
			}
			printf("\n");
		}
	}
	
}