Cod sursa(job #151838)

Utilizator roquerMarinescu Liana roquer Data 8 martie 2008 18:05:43
Problema Triplete Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.86 kb
#include<stdio.h>
#define N 4097
#define M 65537
int n,m;
long long nr;
int a[N+1][N/8+1];
struct muchie
{
	int x,y;
}v[M];
int p2[8]={1,2,4,8,16,32,64,128};
void read()
{
	scanf("%d%d",&n,&m);
	int i,x,y;
	for(i=1;i<=m;++i)
	{
		scanf("%d%d",&x,&y);
		v[i].x=x;
		v[i].y=y;
		--y;
		a[x][y/8]|=p2[y%8];
		++y;
		--x;
		a[y][x/8]|=p2[x%8];
		++x;
	}/*
	for(i=1;i<=n;++i)
	{
		for(int j=0;j<=n/8;++j)
			for(int k=0;k<8;++k)
				if(a[i][j]&p2[k])
					printf("1 ");
				else
					printf("0 ");
		printf("\n");
	}*/
}
void parc()
{
	int i,j;
	for(i=1;i<=m;++i)
	{
		for(j=0;j<=n/8;++j)
		{
			int z=a[v[i].x][j]&a[v[i].y][j];
			while(z)
			{
				++nr;
				z&=(z-1);
			}
		}
	}
	printf("%lld\n",nr/3);
}
int main()
{
	freopen("triplete.in","r",stdin);
	freopen("triplete.out","w",stdout);
	read();
	parc();
	return 0;
}