Cod sursa(job #355422)

Utilizator tamas_iuliaTamas Iulia tamas_iulia Data 10 octombrie 2009 23:53:51
Problema Triplete Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.05 kb
#include <stdio.h>
#include <vector>
#define Nmax 4100
#define Mmax 65540
#define NR 32800
#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[Mmax]; // precalculare
int MASK;

int nrbiti(int x){
	return nr1[x>>16] + nr1[x & MASK];
}

int main(){
	freopen("triplete.in","r",stdin);
   freopen("triplete.out","w",stdout);
   scanf("%d%d",&n,&m);
   MASK = (1<< 16) -1;

   for(i=0;i<(1<<16);++i)
     for(j=0; j<16 && (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++)
            	rez+= nrbiti(a[i][k] & a[j][k]);
     }

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