Cod sursa(job #80589)

Utilizator gigi_becaliGigi Becali gigi_becali Data 28 august 2007 19:14:02
Problema Triplete Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.28 kb
using namespace std;
#include <cstdio>
#include <vector>
#define maxn 4096
#define pb push_back

int n;
vector<int> a[maxn];
unsigned int x[maxn][(maxn/32)+1];
int nrbiti[(1<<16)+1];

void init_biti()
{
	int i, j;
	for(i=0;i<=(1<<16);++i)
	{
		j=i;
		while(j)
		{
			if(j&1) ++nrbiti[i];
			j>>=1;
		}
	}

}

void read()
{
	freopen("triplete.in","r",stdin);
	int m, p,q;
	scanf("%d %d\n", &n, &m);
	
	while(m--)
	{
		scanf("%d %d\n", &p,&q);
		a[p].pb(q);
		//a[q].pb(p);
		x[p][q>>5]|=1<<(q&31);
		x[q][p>>5]|=1<<(p&31);
	}
}

void solve()
{
	int i, j, n32=n/32;
	vector<int>::iterator it;
	unsigned int ax[(maxn/32)+1];
	int nr=0;
	for(i=1;i<=n;++i)
		for(it=a[i].begin();it!=a[i].end();++it)
		{
			for(j=0;j<=n32;++j) ax[j]=x[i][j]&x[*it][j];
			for(j=0;j<=n32;++j) nr+=nrbiti[ax[j]%(1<<16)]+nrbiti[ax[j]>>16];
		//	printf("%d %d\n", i, *it);
			//for(j=1;j<=n;++j) if(ax[j>>5]&(1<<(j&31)))printf("1 ");else printf("0 ");
			//printf("\n");
		}
	printf("%d\n", nr/3);
				
			
	
}

int main()
{
	freopen("triplete.out","w",stdout);
	init_biti();
	read();
	int i,j;
	/*
	for(i=1;i<=n;++i)
	{
		for(j=1;j<=n;++j) if(x[i][j>>5]&(1<<(j&31)))printf("1 ");else printf("0 ");
		printf("\n");
	}
	*/
	
	solve();
	
	return 0;
}