Cod sursa(job #23122)

Utilizator sims_glAlexandru Simion sims_gl Data 28 februarie 2007 10:27:28
Problema Triplete Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.76 kb
#include <stdio.h>

#define nm 5000
#define mm 66000
#define B 30

int n, m, x[mm], y[mm], mat[nm][nm / B];
unsigned int sol;

int nr(int x)
{
	int rez = 0;

	while(x)
    {
    	rez += x % 2;
        x >>= 1;
    }

    return rez;
}

int main()
{
	int i, j;

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

    scanf("%d%d", &n, &m);

	for (i = 1; i <= m; ++i)
    {
    	scanf("%d%d", &x[i], &y[i]);

        mat[x[i]][(y[i] - 1) / B + 1] |= 1 << ((y[i] - 1) % B);
        mat[y[i]][(x[i] - 1) / B + 1] |= 1 << ((x[i] - 1) % B);
    }

    for (i = 1; i <= m; ++i)
    	for (j = 1; j <= n / B + 1; ++j)
        	sol += nr(mat[x[i]][j] & mat[y[i]][j]);

    printf("%u\n", sol / 3);

	return 0;
}