Cod sursa(job #589019)

Utilizator gramatovici_paulGramatovici Paul gramatovici_paul Data 10 mai 2011 17:11:47
Problema Triplete Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.91 kb
#include<cstdio>
using namespace std;


unsigned int a[5000][130];
int n,m,x,y,b,s;


int nrbiti(int n)
{
	int nr=0;
	while(n!=0)
	{
		nr++;
		n&=(n-1);
	}
	return nr;
}


int main()
{
	int i,j;
	freopen("triplete.in","r",stdin);
	freopen("triplete.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(i=1;i<=m;++i)
	{
		scanf("%d%d",&x,&y);
	//	printf("(%d,%d) -> %d\n",x,y,(1<<(y&(31))));
		a[x][y>>5]|=(1<<(y&(31)));
		a[y][x>>5]|=(1<<(x&(31)));
	}
//	for(i=1 ; i<=n ; i++)
//		printf("%d\n",a[i][0]);
	/*
	for(i=1;i<=n;++i)
	{
		for(j=1;j<=n;++j)
		{
//			printf("%d ",(1<<(j&(31))));
			if ( (a[i][j>>5] & (1<<(j&(31)))) !=0)
				printf("1 ");
			else 
				printf("0 ");
		}
		printf("\n");
	}
	*/
	for(x=1;x<=n;++x)
		for(y=x+1;y<=n;++y)
		{
			for(i=0;i<=n>>5;++i)
			{
				b=(a[x][i]&a[y][i]);
				s+=nrbiti(b);
			}
		}
	printf("%d",s/3);
	return 0;
	
	
	
	
	
	
	
}