Cod sursa(job #8035)

Utilizator ProstuStefan-Alexandru Filip Prostu Data 23 ianuarie 2007 18:38:13
Problema Triplete Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 kb
// BRUTE-FORCE
#include <cstdio>

const int NMAX = 4096;
const int DMAX = 128;
const int BMAX = 65536;

int N, M;
unsigned G[NMAX][DMAX];
int A[BMAX], B[BMAX];
int NRBIT[1 << 16];
int cnt;

inline void set1(unsigned G[], int poz) { G[poz >> 5] |= 1u << (poz & 31); }
inline int nrbits(unsigned x) { return NRBIT[x & 65535] + NRBIT[x >> 16]; }

void read() {
	FILE *fin = fopen("triplete.in", "rt");
	int i, j, u, v, stop;

	fscanf(fin, " %d %d", &N, &M);

	stop = (N - 1) >> 5;

	for (i = 0; i < M; ++i) {
		fscanf(fin, " %d %d", &u, &v);
		--u, --v;

		for (j = 0; j <= stop; ++j)
			cnt += nrbits( G[u][j] & G[v][j] );

		set1(G[u], v);
		set1(G[v], u);
	}

	fclose(fin);
}

void bits() {
	int i;

	for (i = 1; i < BMAX; ++i)
		NRBIT[i] = NRBIT[i >> 1] + (i & 1);		
}

void write() {
	FILE *fout = fopen("triplete.out", "wt");

	fprintf(fout, "%d\n", cnt);

	fclose(fout);
}

int main() {

	bits();

	read();

	write();

	return 0;
}