Cod sursa(job #675277)

Utilizator GrimpowRadu Andrei Grimpow Data 7 februarie 2012 15:01:18
Problema Triplete Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.83 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;
}