记录编号	273280	评测结果	AAAAAAAAAA
题目名称	[SYOI 2015] Asm.Def的报告	最终得分	100
用户昵称	sxysxy	是否通过	通过
代码语言	C++	运行时间	0.122 s
提交时间	2016-06-20 14:01:23	内存使用	3.49 MiB

#include <vector>
#include <iostream>
#include <algorithm>
#include <list>
#include <cstring>
#include <string>
#include <queue>
#include <cstdlib>
#include <cstdio>
#include <cctype>
#include <cmath>
using namespace std;
#define MAXN (100001)

int fast_read_int()
{
	int ret = 0;
	char ch;
	bool sig = false;
	while(ch = getchar())
	{
		if(ch == '-')
			sig = true;
		else if(isdigit(ch))
		{
			ret = ch^0x30;
			break;
		}
	}
	while(isdigit(ch = getchar()))ret = (ret << 3)+(ret << 1)+(ch^0x30);
	if(sig) return -ret;
	return ret;
}

class twosat
{
	vector<int> G[MAXN<<1];
	bool mark[MAXN<<1];
	int path[MAXN<<1];
	int path_ptr;
	int n;
public:
	twosat(int mn)
	{
		memset(mark, 0, sizeof(mark));
		memset(path, 0, sizeof(path));
		n = mn;
	}
	void assert(int x, int xv, int y, int yv)
	{
		x = (x<<1)+xv;
		y = (y<<1)+yv;
		G[x^1].push_back(y);
		G[y^1].push_back(x);
	}
	bool dfs(int x)
	{
		if(mark[x^1])return false;
		if(mark[x])return true;
		mark[x] = true;
		path[path_ptr++] = x;
		for(int i = 0; i < G[x].size(); i++)
			if(!dfs(G[x][i])) return false;
		return true;
	}
	void qin_ding(int x)
	{
		if(mark[x])return;
		mark[x] = true;
		mark[x^1] = false;
		for(int i = 0; i < G[x].size(); i++)qin_ding(G[x][i]);
	}
	bool main(FILE *fout)
	{
		for(int i = 1; i <= n; i++)
		{
			int k = i<<1;
			if(!mark[k] && !mark[k^1])
			{
				path_ptr = 0;
				if(dfs(k))
				{
					qin_ding(k);
					//pres_and_exit(fout);
				}
				else
				{
					while(path_ptr > 0)mark[path[--path_ptr]] = false;
					//if(dfs(k^1))
					{
						qin_ding(k^1);
						//pres_and_exit(fout);
					}
				}
				
			}
		}
	}
	void pres_and_exit(FILE *fout)
	{
		for(int i = 1; i <= n; i++)
		{
			int k = i << 1;
			if(mark[k])fputc('0', fout);
			else fputc('1', fout);
			fputc(' ', fout);
		}
		//exit(0);
	}
};

int main()
{
	FILE *fin = fopen("asm_report.in", "r");
	FILE *fout = fopen("asm_report.out", "w");
	int n, m;
	fscanf(fin, "%d %d", &n, &m);
	twosat slv(n);
	while(m--)
	{
		int a, b;
		fscanf(fin, "%d %d", &a, &b);
		int av = a > 0;
		int bv = b > 0;
		a = abs(a);
		b = abs(b);
		slv.assert(a, av, b, bv);
	}
	slv.main(fout);
	slv.pres_and_exit(fout);
	return 0;
}