Cod sursa(job #355366)

Utilizator mihai_floreaFlorea Mihai Alexandru mihai_florea Data 10 octombrie 2009 21:07:01
Problema Triplete Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.86 kb
#include <fstream>
#include <vector>
using namespace std;
typedef unsigned int uint;
const int NMAX=4096;
const int BASE=32;
const int MASK=(1<<(BASE>>1)) - 1;
uint B[NMAX][(NMAX/BASE)+1];
int N,M,HalfBits[1<<(BASE>>1)];
vector<int> G[NMAX];
void add(int i,int j)
{
	B[i][j>>5]|=(1<<(j&31));
	G[i].push_back(j);
}
inline int NrBiti(uint n)
{
	return HalfBits[n&MASK]+HalfBits[n>>16];
}
int main()
{
	int i,j;
	ifstream fin("triplete.in");
	ofstream fout("triplete.out");
	fin>>N>>M;
	while (M--)
	{
		fin>>i>>j;
		i--;j--;
        add(i,j);
		add(j,i);
	}

	for (i=1;i<(1<<(BASE>>1));++i)
       HalfBits[i]=HalfBits[i>>1]+(i&1);

	int CHUNKS=N/BASE,sol=0;
	vector<int>::iterator it;
	for (i=0;i<N;++i)
	  for (it=G[i].begin();it!=G[i].end();++it)
	    for (j=0;j<=CHUNKS;++j)
			sol+=NrBiti(B[i][j]&B[*it][j]);
	fout<<sol/6;
	return 0;
}