Cod sursa(job #59428)

Utilizator peanutzAndrei Homorodean peanutz Data 9 mai 2007 09:59:04
Problema Triplete Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.97 kb
#include <stdio.h>

#define NMAX 4100
#define MMAX 65600
#define INTMAX 33000

int a[NMAX][NMAX/10+60];
int n, m;
int x[MMAX], y[MMAX];
long long nr;
int bit[INTMAX];


void pre()
{
	int i;

	for(i = 1; i < INTMAX; ++i)
	{
		bit[i] = bit[i>>1] + (i&1);
	}
}

void read()
{
	int i;

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

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

		a[ x[i] ][ y[i] / 16 ] |= (1 << (y[i]%16-1));

		a[ y[i] ][ x[i] / 16 ] |= (1 << (x[i]%16-1));
	}
}

void solve()
{
	int i, j;

	for(i = 0; i < m; ++i)
	{
		//a[ x[i] ][ y[i]/16 ] -= (1 << (y[i]%16-1));
		//a[ y[i] ][ x[i]/16 ] -= (1 << (x[i]%16-1));

		for(j = 0; j < NMAX/16+50; ++j)
		{
			nr += bit[ (a[ x[i] ][j] & a[ y[i] ][j]) ];
		}

	}
}

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

	pre();

	read();

	solve();

	printf("%lld\n", nr);

	fclose(stdin);
	fclose(stdout);

	return 0;
}