Cod sursa(job #212174)

Utilizator ProtomanAndrei Purice Protoman Data 4 octombrie 2008 15:47:11
Problema Triplete Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.83 kb
#include <stdio.h>
#include <algorithm>
#define lim_bz2 65535
#define mx 4100

using namespace std;

int x[mx], y[mx];
int v[mx][mx >> 5 + 4];
int nr_biti[lim_bz2 + 4];
int n, m, rez;

int main()
{
	freopen("triplete.in","r",stdin);
	freopen("triplete.out","w",stdout);
	scanf("%ld %ld", &n, &m);
	for (int i = 1; i <= lim_bz2; i++)
		nr_biti[i] = nr_biti[i >> 1] + (i & 1);
	for (int i = 1; i <= m; i++)
	{
		scanf("%ld %ld", &x[i], &y[i]);
		v[x[i]][y[i] >> 5] |= (1 << (y[i] & 31));
		v[y[i]][x[i] >> 5] |= (1 << (x[i] & 31));
	}
	for (int i = 1; i <= m; i++)
		for (int k = 0; k <= (n >> 5) + 1; k++)
		{
			rez += nr_biti[(v[x[i]][k] >> 16) & (v[y[i]][k] >> 16)];
			rez += nr_biti[(v[x[i]][k] & lim_bz2) & (v[y[i]][k] & lim_bz2)];
		}
	printf("%ld\n", rez / 3);
	fclose(stdin);
	fclose(stdout);
	return 0;
}