Cod sursa(job #151813)

Utilizator andreisfrentSfrent Andrei andreisfrent Data 8 martie 2008 17:42:06
Problema Triplete Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.99 kb
#include <stdio.h>

#define max_n 4096
#define max_m 65537

struct muchie
{
	int x, y;
};

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


inline void adauga_relatie(int x, int y)
{
	int grup=y/8+1;
	int pozitie_binara = y%8;
	a[x][grup]|=p2[8-pozitie_binara];
}
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;
		adauga_relatie(x, y);
		adauga_relatie(y, x);
	}
	fclose(stdin);
}

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