Cod sursa(job #354556)

Utilizator tamas_iuliaTamas Iulia tamas_iulia Data 8 octombrie 2009 18:55:47
Problema Triplete Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.05 kb
#include <stdio.h>
#define Nmax 4105
#define Nr 135 // 4096 / 32 -> biti per nr
#define LL long
#define Mmax 65540

int a[Nmax][Nr]; // a[i][j] & (1 << x) =1 => j*32+x e prieten cu i
int n,m,i,j,q,qr,x,y,max,nr,sum,ii;
struct jeg{ int x, y; } v[Mmax];
int vec[Nr];

int main(){
   freopen("triplete.in","r",stdin);
   freopen("triplete.out","w",stdout);
   scanf("%d%d",&n,&m);
   for(i=1;i<=m;++i){
   	scanf("%d%d",&x,&y);
      q=x/32; qr=x%32;
      if(qr>0) q++;
      a[y][q] |= ( 1 << qr );

      q=y/32; qr=y%32;
      if(qr>0) q++;
      a[x][q] |= ( 1 << qr );

		v[i].x=x; v[i].y=y;
   }

   for(i=1;i<=m;++i){
   	x=v[i].x; y=v[i].y;
   	for(j=1;j<Nr;++j) vec[j]=a[x][j] & a[y][j];

      max = x>y ? x : y;
      q=max/32; qr=max%32;
      if(qr>0) q++;

      for(j=qr+1; j<32; j++)
        if(vec[q] & (1<<j)) nr++;
      for(ii=q+1;ii<Nr;++ii)
        for(j=0; j<32; j++)
        		if(vec[ii] & (1<<j) ) nr++;
   }

   printf("%d\n",nr);
   fclose(stdin); fclose(stdout);
   return 0;
}