Cod sursa(job #151852)

Utilizator andreisfrentSfrent Andrei andreisfrent Data 8 martie 2008 18:17:53
Problema Triplete Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.9 kb
#include <stdio.h>

#define max_n 4096
#define max_m 65537
#define ooo sizeof(char)*8

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

int main()
{
	citeste();
	long long int tc=0;
	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("%lld\n",tc/3);
	fclose(stdout);
	return 0;
}