Cod sursa(job #65404)

Utilizator sealTudose Vlad seal Data 9 iunie 2007 13:12:18
Problema Triplete Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.75 kb
#include<stdio.h>
#define Nm 4096
#define Mm 65536
unsigned M[Nm>>5][Nm],X[Mm],Y[Mm],B[Mm],n,m,t;

void read()
{
    int i;

    freopen("triplete.in","r",stdin);
    scanf("%u%u",&n,&m);
    for(i=0;i<m;++i)
	scanf("%u%u",X+i,Y+i);
}

void solve()
{
    unsigned i,j,k;

    for(i=0;i<m;++i)
    {
	--X[i]; --Y[i];
	M[Y[i]>>5][X[i]]|=1u<<(Y[i]&31);
	M[X[i]>>5][Y[i]]|=1u<<(X[i]&31);
    }

    B[0]=0; B[1]=1;
    for(i=2;i<Mm;++i)
	B[i]=B[i>>1]+(i&1);

    for(i=0;i<m;++i)
	for(j=0;j<(n+31)>>5;++j)
	{
	    k=M[j][X[i]]&M[j][Y[i]];
	    t+=B[k&(Mm-1)]+B[k>>16];
	}
}

void write()
{
    freopen("triplete.out","w",stdout);
    printf("%u\n",t/3);
}

int main()
{
    read();
    solve();
    write();
    return 0;
}