Cod sursa(job #355405)

Utilizator tamas_iuliaTamas Iulia tamas_iulia Data 10 octombrie 2009 23:27:33
Problema Triplete Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.12 kb
#include <stdio.h>
#include <vector>
#define Nmax 4097
#define Mmax 65537
#define NR 32769
#define pb push_back
using namespace std;

unsigned int a[Nmax][129]; // 4097 / 32
int i,j,n,m,x,y,rez,k;
vector <int> v[Nmax];
int nr1[NR]; // precalculare

int main(){
	freopen("triplete.in","r",stdin);
   freopen("triplete.out","w",stdout);
   scanf("%d%d",&n,&m);

   for(i=0;i<=(1<<15);++i)
     for(j=0; j<=15 && (1<<j) <=i; j++)
       if(i & (1<<j)) nr1[i]++;

   for(i=1;i<=m;++i){
   	scanf("%d%d",&x,&y);
      a[x][y>>5] |= (1<<(y & 31));
      a[y][x>>5] |= (1<<(x & 31));
      v[x].pb(y);
      v[y].pb(x);
   }

   vector <int>:: iterator it;
   for(i=1;i<=n;++i)
     for(it=v[i].begin(); it!=v[i].end(); it++){
     		j=*it;
         for(k=0;k<129;k++)
         	if(a[i][k] && a[j][k]){
            	x=a[i][k] >> 15;
               y=a[j][k] >> 15;
               rez += nr1[x & y] ;
               rez += nr1[(a[i][k]-(x<<15)) & (a[j][k]-(y<<15))];
            }
     }

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