Cod sursa(job #9192)

Utilizator pauldbPaul-Dan Baltescu pauldb Data 26 ianuarie 2007 23:17:24
Problema Triplete Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.88 kb
#include <stdio.h>

#define maxm 65536
#define maxn 4096
#define maxx 256
#define mod 16

int x[maxm],y[maxm],z[maxm];
int a[maxn][maxx];
int n,m,l,sol;

void update(int x,int y)
{
     a[x][y/mod]+=(1<<(y%mod));
}

int count(int x)
{
    int i,rez=0;
    
    for (i=0;i<mod;i++) 
      if ((x&(1<<i))!=0) rez++;
      
    return rez;
}

int main()
{
    freopen("triplete.in","r",stdin);
    freopen("triplete.out","w",stdout);
    
    scanf("%d %d",&n,&m);
    
    int i,j;
    for (i=0;i<m;i++) 
    {
        scanf("%d %d",&x[i],&y[i]);
        x[i]--;
        y[i]--;
        update(x[i],y[i]);
        update(y[i],x[i]);
    }
        
    for (i=0;i<1<<mod;i++) z[i]=count(i);
           
    l=(n-1)/mod;
    
	for (i=0;i<m;i++)
	  for (j=0;j<=l;j++)
		sol+=z[a[x[i]][j]&a[y[i]][j]];
      
    printf("%d\n",sol/3);
    
    return 0;
}