Cod sursa(job #8359)

Utilizator wefgefAndrei Grigorean wefgef Data 24 ianuarie 2007 17:49:25
Problema Triplete Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.98 kb
#include <cstdio>

#define Nmax 4096

unsigned int vec[Nmax][130];
int nrb[1 << 16];
int n, rez;

void readdata()
{
	freopen("triplete.in", "r", stdin);
	freopen("triplete.out", "w", stdout);
	
	int a, b, m;
	for (scanf("%d %d", &n, &m); m; --m)
	{
		scanf("%d %d", &a, &b);
		--a; --b;
		vec[a][b/32] |= 1 << (b%32);
		vec[b][a/32] |= 1 << (a%32);
	}
}

void eval(int a, int b)
{
	int val = a & b;
	rez += nrb[val & ((1 << 16)-1)];
	rez += nrb[val >> 16];
}

void solve()
{
	int i, j, k, bit;
	
	for (i = 0; i < (1 << 15); ++i)
	{
		nrb[i*2] = nrb[i];
		nrb[i*2+1] = nrb[i]+1;
	}
	
	for (i = 0; i < n; ++i)
		for (j = i+1; j < n; ++j)
			if ((vec[i][j/32] >> (j%32)) & 1)
			{
				bit = j/32;
				for (k = (j%32) + 1; k < 32; ++k)
					if ( ((vec[i][bit] >> k) & (vec[j][bit] >> k)) & 1) ++rez;
				for (k = bit+1; k <= (n-1)/32; ++k)
					eval(vec[i][k], vec[j][k]);
			}
	printf("%d\n", rez);
}

int main()
{
	readdata();
	solve();
	return 0;
}