Cod sursa(job #218278)

Utilizator AndreyPAndrei Poenaru AndreyP Data 1 noiembrie 2008 13:39:31
Problema Triplete Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.9 kb
#include<stdio.h>
#define ll long long
int n,m,unde;
ll r=0;
unsigned int a[4098][130];
void citeste(int &x,int &y)
{
	x=y=0;
	char c[20];
	fgets(c,20,stdin);
	int i;
	for(i=0; c[i]>='0' && c[i]<='9'; i++)
		x=x*10+c[i]-'0';
	for(i++; c[i]>='0' && c[i]<='9'; i++)
		y=y*10+c[i]-'0';
}
void citire()
{
	int x,y;
	for(int i=0; i<m; i++)
	{
		citeste(x,y);
		if(y<x)
			a[y][x>>5]|=1<<(x&31);
		else
			a[x][y>>5]|=1<<(y&31);
	}
	unde=(n>>5)+1;
}
long long nrb(unsigned int x)
{
	int k=0;
	while(x)
	{
		x&=x-1;
		k++;
	}
	return (ll)k;
}
void vezi(int x,int y)
{
	unsigned int aux;
	if(!(a[x][y>>5]&(1<<(y&31))))
		return;
	for(int i=0; i<unde; i++)
	{
		aux=a[x][i]&a[y][i];
		r+=nrb(aux);
	}
}
int main()
{
	freopen("triplete.in","r",stdin);
	freopen("triplete.out","w",stdout);
	scanf("%d%d\n",&n,&m);
	citire();
	int i,j;
	for(i=1; i<=n; i++)
	{
		for(j=i+1; j<=n; j++)
			vezi(i,j);
	}
	printf("%lld\n",r);
	return 0;
}