Cod sursa(job #14638)

Utilizator megabyteBarsan Paul megabyte Data 9 februarie 2007 13:03:06
Problema Triplete Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.21 kb
#include <stdio.h>
#define INF "triplete.in"
#define OUF "triplete.out"
#define NMAX 4096
//int mask[32],bit[NMAX][128]={0},n,m,lim;
struct muchie
{
       int x,y;
};//ark[65538];
/*unsigned long long triplete(int a,int b)
{
   register int d,r,i,j,aux;
   unsigned long long nr=0;
   for(i=0;i<lim;i++)
   {
	   aux=bit[a][i]&bit[b][i];
	   for(j=0;j<32;j++)
		   if(aux&mask[j]) nr++;
   }
   return nr;
}*/
int main()
{
        int mask[32],bit[NMAX][128]={0},n,m,lim;
	muchie ark[65536];
	register int aux,k,i,j,a,b,d,r,sum=0;
	FILE *in,*out;
	in=fopen(INF,"r");
	out=fopen(OUF,"w");
	fscanf(in,"%d %d",&n,&m);
	mask[0]=1;lim=n/32+1;
	if(lim>128) lim=128;
	for(i=1;i<32;i++) mask[i]=(1<<i);
	for(i=0;i<m;i++)
	{
		fscanf(in,"%d %d",&a,&b);
		a--;b--;// 0 indexing
		d=b/32;r=b%32;//printf("%d %d\n",d,r);
		bit[a][d]=bit[a][d]|mask[r];// b in lista lui a
		d=a/32;r=a%32;//printf("%d %d\n",d,r);
		bit[b][d]=bit[b][d]|mask[r];// a in lista lui b
		ark[i].x=a;ark[i].y=b;
	}
	for(k=0;k<m;k++)
	{
	
	a=ark[k].x;b=ark[k].y;
	for(i=0;i<lim;i++)
        {
	   aux=bit[a][i]&bit[b][i];
	   while(aux)
	   {
		   sum++;
		   aux=aux&(aux-1);
	   }
        }
	}
     	sum=sum/3;
	fprintf(out,"%d",sum);
	fclose(in);fclose(out);
	return 0;
}