Cod sursa(job #341559)

Utilizator rumburakrumburak rumburak Data 18 august 2009 19:48:01
Problema Triplete Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.86 kb
#include<cstdio>

const int N = (1<<12);
const int d = (1<<3);

int n;
unsigned char a[N][N>>3];

void citire()
{
	int m,x,y;
	scanf("%d%d",&n,&m);
	while(m--)
	{
		scanf("%d%d",&x,&y);
		--x;
		--y;
		a[x][y/d] |= 1<<(y%d);
		a[y][x/d] |= 1<<(x%d);
	}
}

void proba()
{
	for(int i=0;i<n;++i)
	{
		for(int j=0;j<n;++j)
			printf("%3d",a[i][j/d] & (1<<(j%d)) ? 1 : 0);
		printf("\n");
	}
}

int biti1(unsigned char x)
{
	int nr=0;
	while(x)
	{
		++nr;
		x &= x-1;
	}
	return nr;
}

long long calcul()
{
	int i,j,k;
	long long nr=0;
	for(i=0;i<n;++i)
		for(j=0;j<n;++j)
			if(i!=j)
				for(k=0;k<=n/d;++k)
					nr+=(long long)biti1(a[i][k]&a[j][k]);
	return nr/6;
}

int main()
{
	freopen("triplete.in","r",stdin);
	freopen("triplete.out","w",stdout);
	citire();
	printf("%lld\n",calcul());
	//proba();
	return 0;
}