Cod sursa(job #404282)

Utilizator cosmin79Carabet Cosmin Andrei cosmin79 Data 25 februarie 2010 23:42:12
Problema Triplete Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.94 kb
#include <stdio.h>
#define NMAX 4101
#define LMAX 65601
#define HMAX 261
#define KMAX 1<<16
int n,m;
struct muchie
{
	int a,b;
};
muchie A[LMAX];
int mat[NMAX][HMAX],nrb[KMAX],rez;
void read()
{
	scanf("%d%d",&n,&m);
	int i,x,y;
	for (i=1; i<=m; i++)
	{
		scanf("%d%d",&A[i].a,&A[i].b);
		x=A[i].b>>4; y=A[i].b-(x<<4);
		mat[A[i].a][x]+=1<<y;
		x=A[i].a>>4; y=A[i].a-(x<<4);
		mat[A[i].b][x]+=(1<<y);
	}
}
void precompute()
{
	int i,nr=(1<<16);
	for (i=1; i<nr; i++)
		nrb[i]=nrb[(i>>1)]+(i & 1);
}
void solve()
{
	int i,j,x,y,t;
	t=n>>4;
	for (i=1; i<=m; i++)
	{
		x=A[i].b>>4; y=A[i].b-(x<<4);
		mat[A[i].a][x]-=(1<<y);
		x=A[i].a>>4; y=A[i].a-(x<<4);
		mat[A[i].b][x]-=(1<<y);
		for (j=0; j<=t; j++)
			rez+=nrb[mat[A[i].a][j] & mat[A[i].b][j]];
	}
}
int main()
{
	freopen("triplete.in","r",stdin);
	freopen("triplete.out","w",stdout);
	read();
	precompute();
	solve();
	printf("%d\n",rez);
	return 0;
}