Cod sursa(job #1146035)

Utilizator cosmin.pascaruPascaru Cosmin cosmin.pascaru Data 18 martie 2014 17:31:31
Problema Triplete Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.97 kb
#include <cstdio>
#include <climits>

using namespace std;

struct muchie
{
    int x, y;
} m[65540];

int N, M;
int p2[65540];
int a[4100][260];

void citire()
{
    int x,y;

    scanf("%d %d", &N, &M);
    for (int i = 0; i < M; ++i)
    {
        scanf("%d %d", &x, &y);
        m[i].x = x;
        m[i].y = y;

        a[x][y >> 4]|=1 << ( y %(1 << 4) );
        a[y][x >> 4]|=1 << ( x %(1 << 4) );
    }
}

void preprocessing()
{
    int pmax = 1<<16, aux;
    for (int i = 0; i <= pmax; ++i)
        for (aux = i; aux; aux &= aux-1)
            ++p2[i];
}

long long solve()
{
    long long sol=0;
    for (int i = 0; i <= M; ++i)
    {
        for (int j = 0; j < 256; ++j)
            sol += p2[ a[ m[i].x ][j] & a[ m[i].y ][j] ];
    }
    return sol/3;
}
int main()
{
	freopen("triplete.in", "r", stdin);
	freopen("triplete.out", "w", stdout);


    citire();
    preprocessing();
    printf("%d\n", solve());

	return 0;
}