Cod sursa(job #206175)

Utilizator anna_bozianuBozianu Ana anna_bozianu Data 5 septembrie 2008 10:32:43
Problema Triplete Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.71 kb
#include<stdio.h>
int n,m,i,j,k,c1,c2,a[65536],b[65536],x[4096][256],col[4096],bit[4096];//4096,256
long long sol,nb[65],cnt[65];//65535
int main()
{       freopen("triplete.in","r",stdin);
	freopen("triplete.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(i=0;i<n;i++)
	 { col[i]=i>>4;bit[i]=i&15;bit[i]=1<<bit[i];}
	c2=col[n-1];
	for(i=0;i<m;i++)
	{ scanf("%d%d",&j,&k);j--;k--;
	  if(j<k){ a[i]=j;b[i]=k;x[j][col[k]]+=bit[k];}
	  else { a[i]=k;b[i]=j;x[k][col[j]]+=bit[j];}
	}
	for(i=1;i<65536;i++)nb[i]=nb[i/2]+i%2;
	for(i=0;i<m;i++)
	{ j=a[i];k=b[i];
	  c1=col[k];
	  for(cc=c1;cc<=c2;cc++)
	   cnt[x[j][cc]&x[k][cc]]++;
	}
	for(i=1;i<65536;i++)
	 sol+=cnt[i]*nb[i];
	printf("%lld",sol);
	return 0;
}