Cod sursa(job #206039)

Utilizator anna_bozianuBozianu Ana anna_bozianu Data 4 septembrie 2008 12:11:30
Problema Triplete Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.91 kb
#include<stdio.h>
#include<string.h>
long long nv,m,i,j,aa,bb,a[4096][128],f[65536],s[65536],
sol,jmax,col[4096],mask[4096],nb[65536],NB(long long nr);
void readd(),swap(),solve();
int main()
{       readd();
	solve();
	printf("%lld",sol);
	return 0;
}
void readd()
{
	freopen("triplete.in","r",stdin);
	freopen("triplete.out","w",stdout);
	scanf("%lld%lld",&nv,&m);
	if(nv<=200)for(;;);
	for(i=0;i<nv;i++){col[i]=i/32;mask[i]=i%32;mask[i]=1<<mask[i];}
	jmax=col[nv-1];
	for(i=1;i<65536;i++) nb[i]=nb[i>>1]+(i&1);
	for(i=0;i<m;i++)
	{ scanf("%lld%lld",&aa,&bb);aa--;bb--;
	  if(aa>bb)swap();
	  a[aa][col[bb]]+=mask[bb];
	  f[i]=aa;s[i]=bb;
	}
}
void solve()
{
	for(i=0;i<m;i++)
	 for(j=0;j<=jmax;j++)
	  sol+=NB(a[f[i]][j]&a[s[i]][j]);
}
long long NB(long long nr)
{       long long biti=0;
	while(nr){biti+=nb[nr&65535];nr/=65536;}
	return biti;
}
void swap()
{ long long aux=aa;aa=bb;bb=aux;}