Cod sursa(job #8320)

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

#define Nmax 4096

int vec[Nmax][128];
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 ((v[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;
}