Cod sursa(job #220370)

Utilizator gabitzish1Gabriel Bitis gabitzish1 Data 10 noiembrie 2008 17:02:58
Problema Triplete Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.19 kb
#include <cstdio>
#include <vector>
using namespace std;

int n, m;
int contor;

int v[4100][140];

typedef struct
{
	int x, y;
} Muchie;
Muchie a[66000];

void citire()
{
	freopen("triplete.in","r",stdin);
	freopen("triplete.out","w",stdout);
	
	int i, g, r, j;
	char s[100];
	fgets(s,90,stdin);
	i = 0;
	while (s[i] <= '9' && s[i] >= '0')
	{
		n = n * 10 + s[i] - '0';
		i++;
	}
	i++;

	while (s[i] <= '9' && s[i] >= '0')
	{
		m = m * 10 + s[i] - '0';
		i++;
	}
	
	for (i = 1; i <= m; i++)
	{
		fgets(s,90,stdin);
	
		j = 0;
		while (s[j] <= '9' && s[j] >= '0')
		{
			a[i].x = a[i].x * 10 + s[j] - '0';
			j++;
		}
		j++;
		while (s[j] <= '9' && s[j] >= '0')
		{
			a[i].y = a[i].y * 10 + s[j] - '0';
			j++;
		}


		g = a[i].y / 31;
		r = a[i].y % 31;
		v[a[i].x][g] += (1<<r);

		g = a[i].x / 31;
		r = a[i].x % 31;
		v[a[i].y][g] += (1<<r);	
	}
}

int nrb(int x)
{
	int cnt = 0;
	while (x)
	{
		cnt += (x % 2);
		x /= 2;
	}
	return cnt;
}

int main()
{
	citire();
	int i, j;

	for (i = 1; i <= m; i++)
		for (j = 0; j <= n / 31; j++)
			contor += nrb(v[a[i].x][j] & v[a[i].y][j]);			
	printf("%d\n",contor / 3);
	return 0;
}