Cod sursa(job #13996)

Utilizator victorsbVictor Rusu victorsb Data 7 februarie 2007 23:39:47
Problema Triplete Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.03 kb
#include <cstdio>

#define Nmax 4100
#define Mmax 65540

int n, m, i, j, mask, ct, sol, l;
unsigned short lv[Nmax][(Nmax / 16) + 1];
int nr1[1 << 16];
int ma[Mmax], mb[Mmax];


void citire()
{
    int v;
    scanf("%d %d\n", &n, &m);
    for (i=1; i<=m; ++i)
    {
        scanf("%d %d\n", &ma[i], &mb[i]);
        v = mb[i] - 1;
        lv[ma[i]][(mb[i] - 1) / 16] += 1 << ((mb[i] - 1) % 16);
        lv[mb[i]][(ma[i] - 1) / 16] += 1 << ((ma[i] - 1) % 16);
    }
}

void preproc()
{
    for (mask = 0; mask < 1<<16; ++mask)
    {
        ct = 0;
        for (i=0; i<16; ++i)
            if ((mask >> i) & 1)
                ++ct;
        nr1[mask] = ct;
    }
}

void solve()
{
    preproc();
    l = (n / 16) + 1;
    for (i=1; i<=m; ++i)
        for (j = 0; j < l; ++j)
            sol += nr1[lv[ma[i]][j] & lv[mb[i]][j]];
    printf("%d\n", sol / 3);
}

int main()
{
    freopen("triplete.in", "r", stdin);
    freopen("triplete.out", "w", stdout);
    citire();
    solve();
    return 0;
}