Cod sursa(job #151863)

Utilizator andreisfrentSfrent Andrei andreisfrent Data 8 martie 2008 18:22:34
Problema Triplete Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.73 kb
#include <stdio.h>

#define max_n 4096
#define max_m 65537

int tc;

struct muchie
{
	int x, y;
};

int p2[8] = {1,2,4,8,16,32,64,128};
muchie vm[max_m+1];
int a[max_n+1][max_n/8+1];
int n,m;

inline void citeste()
{
	freopen("triplete.in","r",stdin);
	scanf("%d %d\n",&n,&m);
	int i,x,y;
	for(i=1;i<=m;++i)
	{
		scanf("%d %d\n",&x,&y);
		vm[i].x=x;
		vm[i].y=y;
		a[x][y/8+1]|=p2[y%8];
		a[y][x/8+1]|=p2[x%8];
	}
	fclose(stdin);
}

int main()
{
	citeste();
	int i,k,z;
	for(k=1;k<=m;++k)
	{
		for(i=1;i<=n/8+1;++i)
		{
			z=a[vm[k].x][i]&a[vm[k].y][i];
			while(z)
			{
				z=z&(z-1);
				++tc;
			}
		}
	}
	freopen("triplete.out","w",stdout);
	printf("%d\n",tc/3);
	fclose(stdout);
	return 0;
}