记录编号	583605	评测结果	AAAAA
题目名称	POJ 3678]卡图难题	最终得分	100
用户昵称	┭┮﹏┭┮	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2023-10-19 17:18:26	内存使用	0.00 MiB

#include <bits/stdc++.h> 
using namespace std;
const int N = 2e3+10,M = 4e6+10;
int n,m;
struct made{
	int ver,nx;
}e[M];
int hd[N],tot,cnt,num,top;
int low[N],dfn[N],st[N],color[N];
bool v[N];
void add(int x,int y){
	tot++;
	e[tot].ver = y,e[tot].nx = hd[x];hd[x] = tot;
}
void tarjan(int x){
	low[x] = dfn[x] = ++cnt;
	st[++top] = x,v[x] = 1;
	for(int i = hd[x];i;i = e[i].nx){
		int y = e[i].ver;
		if(!dfn[y])tarjan(y),low[x] = min(low[x],low[y]);
		else if(v[y])low[x] = min(low[x],dfn[y]);
	}
	if(low[x] == dfn[x]){
		num++;int y = 0;
		do{
			y = st[top--];
			v[y] = 0,color[y] = num;
		}while(x != y);
	}
}
int main(){
	freopen("katu.in","r",stdin);
	freopen("katu.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i = 1;i <= m;i++){
		int x,y,p;char op[10];
		scanf("%d%d%d%s",&x,&y,&p,op);
		if(op[0] == 'A'){
			if(p == 1){//x&&y=1
				add(x,x+n);
				add(y,y+n);
			}
			else{//x&&y = 0
				add(x+n,y);
				add(y+n,x);
			}
		}
		else if(op[0] == 'O'){
			if(p == 1){//x||y=1
			    add(x,y+n);
			    add(y,x+n);
			}
			else{//x||y=0
				add(x+n,x);
				add(y+n,y);
			}
		}
		else{
			if(p == 1){//x^y=1
				add(x,y+n);
				add(y,x+n);
				add(x+n,y);
				add(y+n,x);
			}
			else{//x^y=0
				add(x,y);
				add(y,x);
				add(x+n,y+n);
				add(y+n,x+n);
			}
		}
	}
	for(int i = 1;i <= 2*n;i++)
	    if(!color[i])tarjan(i);
	for(int i = 1;i <= n;i++){
		if(color[i] == color[i+n]){
			printf("NO\n");
			return 0;
		}
	}
	printf("YES\n");
	
	return 0;
	
}