Cod sursa(job #397463)

Utilizator andrei.sfrentSfrent Andrei andrei.sfrent Data 16 februarie 2010 23:14:16
Problema Triplete Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 0.99 kb
#include <stdio.h>

#define N 4096
#define M 65536

typedef struct { int x, y; } muchie;

muchie vm[M + 1];
unsigned char a[N + 1][N / 8];
int m, n;
unsigned int t = 0;

inline void add(int x, int y)
{
	if(y % 8 == 0) a[x][(y - 1) / 8] |= 0x01;
	else a[x][(y - 1) / 8] |= (1 << (8 - (y % 8)));
}

void citeste()
{
	int i, x, y;
	scanf("%d%d", &n, &m);
	for(i = 0; i < m; ++i)
	{
		scanf("%d%d", &x, &y);

		vm[i].x = x;
		vm[i].y = y;
		
		add(x, y);
		add(y, x);
	}
}

void scrie()
{
	printf("%u\n", t / 3);
}

int nrbiti(unsigned char x)
{
	int r = 0, rx = x;
	while(x)
	{
		r += (x % 2);
		x /= 2;
	}
	return r;
}

int nb[256];
void preproceseaza()
{
	unsigned char i;
	for(i = 0; i < 255; ++i) nb[i] = nrbiti(i);
	nb[255] = 8;
}

void rezolva()
{
	int i, j;
	for(i = 0; i < m; ++i) for(j = 0; j < N / 8; ++j) t += nb[a[vm[i].x][j] & a[vm[i].y][j]];
}

int main()
{
	freopen("triplete.in", "r", stdin);
	freopen("triplete.out", "w", stdout);
	preproceseaza();
	citeste();
	rezolva();
	scrie();
	return 0;
}