Cod sursa(job #7485)

Utilizator gcosminGheorghe Cosmin gcosmin Data 21 ianuarie 2007 16:10:55
Problema Triplete Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.76 kb
#include <stdio.h>

#define NMAX 4100
#define MMAX 66000

const int mod16 = (1 << 16) - 1;

int N, M;

int xx[MMAX];
int yy[MMAX];

int nrb[(1 << 16) + 100];

unsigned int leg[NMAX][(NMAX >> 5) + 3];

inline void put(int x, int y)
{
	leg[x][y >> 5] |= 1 << (y & 31);
}

inline unsigned int ex(int x, int y)
{
	return (leg[x][y >> 5] & (1 << (y & 31)));
}

inline int nrb1(unsigned int x)
{
	return nrb[x & mod16] + nrb[(x >> 16)];
}

/*
int solve_brute()
{
	int i, j, k, rez = 0;

	for (i = 1; i <= N; i++)
		for (j = i + 1; j <= N; j++)
			for (k = j + 1; k <= N; k++)
				if (ex(i, j) && ex(i, k) && ex(j, k)) rez++;

	return rez;
}

unsigned int legtemp[NMAX][(NMAX >> 5) + 3];

#include <stdlib.h>
int gen(int N, int M)
{
	freopen("triplete.in", "w", stdout);

	printf("%d %d\n", N, M);	

	int x, y;
	for (int i = 1; i <= M; ) 
	{
		x = rand() % N + 1; y = rand() % N + 1;
		if (x == y) continue;
		if (legtemp[x][y >> 5] & (1 << (y & 31))) continue;

		legtemp[x][y >> 5] |= 1 << (y & 31);
		legtemp[y][x >> 5] |= 1 << (x & 31);

		printf("%d %d\n", x, y);

		i++;
	}

fclose(stdout);
return 0;
}
*/

int main()
{
//	srand(13);
//	gen(4000, 65000);

	int i, x, y;
	
	freopen("triplete.in", "r", stdin);
	freopen("triplete.out", "w", stdout);

	nrb[0] = 0;

	for (i = 1; i <= (1 << 16); i++)
		nrb[i] = nrb[i >> 1] + (i & 1);

	scanf("%d %d", &N, &M);

	for (i = 1; i <= M; i++) {
		scanf("%d %d", &xx[i], &yy[i]);

		put(xx[i], yy[i]);
		put(yy[i], xx[i]);
	}

	int q, j;
	long long rez = 0;
	unsigned int aux;
	for (i = 1; i <= M; i++) {
		x = xx[i]; y = yy[i];

		q = 0;
		for (j = 0; j < (N >> 5) + 3; j++) {
			aux = leg[x][j] & leg[y][j];

			q += nrb1(aux);
		}

		rez += q;
	}

	printf("%lld\n", rez / 3);

//	printf("%d\n", solve_brute());

fclose(stdin);
fclose(stdout);
return 0;	
}