Cod sursa(job #1759388)

Utilizator silkMarin Dragos silk Data 18 septembrie 2016 23:44:14
Problema Triplete Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.95 kb
#include <cstdio>
#define LMax 65536
#define NMax 4096
#define VMax 128
#define uint unsigned int

uint T[NMax+2][VMax+2];
uint nr[LMax+2];
int a[LMax+2];
int b[LMax+2];

int count(int x)
{
    return nr[ x>>16 ] + nr[ x & (LMax-1) ];
}

void add(int i,int j)
{
    T[i][j/32] |= 1<<(j%32);
}

void Precalc()
{
    int i,j,x;
    for(i = 1; i <= LMax-1; ++i)
        for(x = i; x; x=x>>1)
        if( x&1 ) ++nr[i];
}

int main(){
    freopen("triplete.in","r",stdin);
    freopen("triplete.out","w",stdout);

    Precalc();

    int i,j,x,y,N,M;
    long long ans = 0;

    scanf("%d %d",&N,&M);
    for(i = 1; i <= M; ++i)
    {
        scanf("%d %d", &a[i], &b[i]);
        add(a[i],b[i]);
        add(b[i],a[i]);
    }

    for(i = 1; i <= M; ++i)
    {
        x = a[i]; y = b[i];
        for(j = 0; j <= N/32; ++j)
        ans += count( T[x][j]&T[y][j] );
    }

    printf("%lld\n", ans/3);



return 0;
}