Cod sursa(job #397456)

Utilizator andrei.sfrentSfrent Andrei andrei.sfrent Data 16 februarie 2010 22:59:42
Problema Triplete Scor 50
Compilator c Status done
Runda Arhiva de probleme Marime 0.9 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;
long long 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("%lld\n", t / 3);
}

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

void rezolva()
{
	int i, j, x, y;
	for(i = 0; i < m; ++i) //fiecare muchie
	{
		x = vm[i].x;
		y = vm[i].y;

		for(j = 0; j < N / 8; ++j) t += nrbiti(a[x][j] & a[y][j]);
	}
}

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