Cod sursa(job #219889)

Utilizator RegeleUmbrelorPopescu Mihai RegeleUmbrelor Data 8 noiembrie 2008 16:09:05
Problema Triplete Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.77 kb
#include<stdio.h>
const unsigned int NMAX=4200;
unsigned int N,M, a[NMAX][NMAX/32+1];
unsigned long long rez=0;
unsigned int nrb(unsigned int x)
{
	unsigned int nr=0;
	while(x)
	{
		x&=x-1;
		++nr;
	}
	return nr;
}


void citire()
{
	unsigned int x,y;
	freopen("triplete.in","r", stdin);
	scanf("%u%u",&N,&M);
	while(M--)
	{
		scanf("%u%u",&x,&y);
		if(x>y)
		{
			x+=y;
			y=x-y;
			x-=y;
		}
		--x;--y;
		a[x][y>>5]|=1<<(y&31);
	}
}

void calcul()
{
	unsigned int i,j,k;
	for(i=0;i<N-2;++i)
		for(j=i+1;j<N-1;++j)
			if(a[i][j>>5]&(1<<(j&31)))
				for(k=0;k<=(N>>5);++k)
					rez+=(unsigned long long)nrb(a[i][k]&a[j][k]);
}

int main()
{
	freopen("triplete.out","w",stdout);
	citire();
	calcul();
	printf("%llu\n",rez);
	return 0;
}