Cod sursa(job #65407)

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

void read()
{
    char S[12];
    int i;

    freopen("triplete.in","r",stdin);
    scanf("%u%u\n",&n,&m);
    for(i=0;i<m;++i)
    {
	gets(S);
	X[i]=atoi(strtok(S," "));
	Y[i]=atoi(strtok(NULL," "));
    }
}

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

    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);

    l=(n+31)>>5;
    for(i=0;i<m;++i)
	for(j=0;j<l;++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;
}