Cod sursa(job #220363)

Utilizator gabitzish1Gabriel Bitis gabitzish1 Data 10 noiembrie 2008 16:47:05
Problema Triplete Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.85 kb
#include <cstdio>
#include <vector>
using namespace std;

int n, m;
long contor;

long v[4100][140];

typedef struct
{
	int x, y;
} Muchie;
Muchie a[66000];

void citire()
{
	freopen("triplete.in","r",stdin);
	freopen("triplete.out","w",stdout);
	
	int i, x, y, g, r;
	scanf("%d %d",&n, &m);
	for (i = 1; i <= m; i++)
	{
		scanf("%d %d", &x, &y);

		g = y / 30;
		r = y % 30;
		v[x][g] += (1<<r);

		g = x / 30;
		r = x % 30;
		v[y][g] += (1<<r);		
		a[i].x = x; a[i].y = y;
	}
}

int nrb(long x)
{
	int cnt = 0;
	while (x)
	{
		cnt += (x % 2);
		x /= 2;
	}
	return cnt;
}

int main()
{
	citire();
	int i, j;
	long x;

	for (i = 1; i <= m; i++)
		for (j = 0; j <= n / 30 + 1; j++)
		{
			x = (v[a[i].x][j] & v[a[i].y][j]);
			contor += nrb(x);
		}



	contor /= 3;

	printf("%ld\n",contor);
	return 0;
}