Cod sursa(job #11359)

Utilizator devilkindSavin Tiberiu devilkind Data 31 ianuarie 2007 14:20:18
Problema Triplete Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.33 kb
#include <stdio.h>
#define NMAX 4098
#define MMAX 1 << 16

FILE *f = fopen("triplete.in","rt"), *g = fopen("triplete.out","wt");

struct lista{long int nod;
             lista *urm;} *vf[NMAX];     

long int n,m,a[NMAX][300],k,x,y,much[MMAX][2],ymax,nr[MMAX],i,j;

int muc(long int x, long int y)
{
lista *p;
p=new lista;
p=vf[x];
while (p)
      {if (p->nod==y) return 1;
      p=p->urm;
      }
return 0;
}

void citire()
{
fscanf(f,"%ld %ld",&n,&m);
lista *p;
for (i=1;i<=m;i++)     
    {fscanf(f,"%ld %ld",&x,&y);
    much[i][0]=x;
    much[i][1]=y;
    p=new lista;
    p->nod=x;
    p->urm=vf[y];
    vf[y]=p;
    
    p=new lista;
    p->nod=y;
    p->urm=vf[x];
    vf[x]=p;
    }
    
for (i=1;i<=n;i++)
    {
    k=16;
    y=1;
    while (k<=m+16)
	{x=1;
	x=(x<<1) + muc(i,k);
        for (j=k-1;j%16;j--)
                x=(x << 1) + muc(i,j);
        a[i][y]=x;
        y++;
        k+=16;}
    }
ymax=y-1;    
     
}

void solve()
{
long int x,y,sol,s;
sol=0;
for (i=1;i<=m;i++)
    {
    s=0;
    x=much[i][0];
    y=much[i][1];
    for (j=1;j<=ymax;j++)
        s+=nr[a[x][j]&a[y][j]];
    sol+=s-1;
    }
fprintf(g,"%ld",sol/3);
}

int main()
{
citire();
for (i=1;i <= (1 << 17) - 1;i++)
    nr[i]=nr[i/2]+i%2;
solve();
fclose(f);
fclose(g);
return 0;
}