Cod sursa(job #341734)

Utilizator rumburakrumburak rumburak Data 19 august 2009 13:39:36
Problema Triplete Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.87 kb
#include<cstdio>
#include<vector>

using namespace std;

const int N = (1<<12);

unsigned int n;
unsigned char a[N][N>>3];
vector<short int> adj[N];

void citire()
{
	unsigned int m;
	short int x,y;
	scanf("%u%u",&n,&m);
	while(m--)
	{
		scanf("%hd%hd",&x,&y);
		--x;
		--y;
		a[x][y>>3] |= 1<<(y&7);
		a[y][x>>3] |= 1<<(x&7);
		adj[x].push_back(y);
	}
}


inline unsigned int biti_1(unsigned char x)
{
	unsigned int nr=0;
	while(x)
	{
		++nr;
		x &= x-1;
	}
	return nr;
}


unsigned int calcul()
{
	unsigned int i,j,k,m,nb=1+(n>>3);
	long long nr=0;
	for(i=0;i!=n;++i)
		for(j=0,m=adj[i].size();j!=m;++j)
			for(k=0;k!=nb;++k)
				nr+=(long long)biti_1(a[i][k]&a[adj[i][j]][k]);
	return nr/3;
}

int main()
{
	freopen("triplete.in","r",stdin);
	freopen("triplete.out","w",stdout);
	citire();
	printf("%lld\n",calcul());
	return 0;
}