Cod sursa(job #355484)

Utilizator tamas_iuliaTamas Iulia tamas_iulia Data 11 octombrie 2009 12:13:28
Problema Triplete Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.13 kb
#include <stdio.h>
#include <vector>
#define Nmax 4100
#define Mmax 65540
#define NR 32800
#define pb push_back
#define ll long 
using namespace std;

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

int nrbiti(unsigned 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++)
         	if(a[i][k] && a[j][k])
            	rez+= nrbiti(a[i][k] & a[j][k]);
            
     }

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