Cod sursa(job #467863)

Utilizator andrei.dAndrei Diaconeasa andrei.d Data 30 iunie 2010 23:54:01
Problema Party Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.87 kb
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <vector>

using namespace std;

#define file_in "party.in"
#define file_out "party.out"

#define nmax 232133

int n,m;
vector<int> G[nmax];
vector<int> Gt[nmax];
int ok,nr;
int viz[nmax];
int sol[nmax];
int ord[nmax];


inline int neg(int a)
{
    if (a>n)
        return a-n;
    else
        return a+n;
}

void baga(int x, int y)
{
	G[2*n-x+1].push_back(y);
    G[2*n-y+1].push_back(x);
	Gt[y].push_back(2*n-x+1);
	Gt[x].push_back(2*n-y+1);
}


void citire()
{
    int i,a,b,c;
    freopen(file_in,"r",stdin);
    freopen(file_out,"w",stdout);

    scanf("%d %d", &n, &m);
    while(m--)
    {
        scanf("%d %d %d", &a, &b,&c);
        if (c==0)
        baga(a,b);
        else
        if (c==1)
        baga(a,2*n-b+1);
        else
        if (c==2)
        baga(2*n-a+1,b);
        else
        baga(2*n-a+1,2*n-b+1);
    }

}

void dfs(int nod)
{
	int i;
	if (viz[nod])
		return ;
	viz[nod]=1;
	for (i=0;i<G[nod].size();++i)
		 if (!viz[G[nod][i]])
			 dfs(G[nod][i]);
	ord[++nr]=nod;
}

void dfst(int nod)
{
	int i;
	if (viz[nod])
		return ;
	viz[nod]=1;
	if (sol[nod]) ok=0;
	sol[neg(nod)]=1;
	for (i=0;i<Gt[nod].size();++i)
		 if (!viz[Gt[nod][i]])
			 dfst(Gt[nod][i]);
}


void solve()
{
    int i;
    ok=1;
    nr=0;
    for (i=1;i<=2*n;++i)
          if (!viz[i])
             dfs(i);
    memset(viz,0,sizeof(viz));
    for (i=2*n;i>=1;--i)
         if (!viz[ord[i]] && !viz[neg(ord[i])])
             dfst(ord[i]);
    nr=0;
    for (i=1;i<=n;++i)
         if (sol[i]) nr++;
         printf("%d\n", nr);
    for (i=1;i<=n;++i)
          if (sol[i]);
          printf("%d\n", sol[i]);
}

int main()
{
    citire();
    solve();

    fclose(stdin);
    fclose(stdout);

    return 0;
}