Cod sursa(job #324134)

Utilizator GavrilaVladGavrila Vlad GavrilaVlad Data 14 iunie 2009 18:28:48
Problema Triplete Scor 100
Compilator cpp Status done
Runda biti Marime 0.84 kb
#include <stdio.h>

#define maxn 4200
#define maxm 66600
#define nbit 16

using namespace std;

long n, m, i, j, k, sol, a[maxm], b[maxm], x, v[maxn][maxn/nbit];
long p[1<<nbit];

int main()
{
    freopen("triplete.in", "r", stdin);
    freopen("triplete.out", "w", stdout);
    scanf("%d%d", &n, &m);
    for(i=1; i<=m; i++)
    {
        scanf("%d%d", &a[i], &b[i]);
        v[a[i]][b[i]/nbit]+=(1<<(b[i]%nbit));
        v[b[i]][a[i]/nbit]+=(1<<(a[i]%nbit));
    } 
    for(i=0; i<1<<nbit; i++) 
    {
        x=i; 
        while(x)
        {
            x=x&(x-1);
            p[i]++;
        }
    }   
    for(i=1; i<=m; i++)
    {
        for(j=0; j<=(n/nbit); j++)
        {
            x=v[a[i]][j]&v[b[i]][j];
            sol+=p[x];
        }
    }
    printf("%d\n", sol/3);
    return 0;
}