Cod sursa(job #355362)

Utilizator mihai_floreaFlorea Mihai Alexandru mihai_florea Data 10 octombrie 2009 20:59:42
Problema Triplete Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.89 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)
{
	int c,r;
	c=j/BASE;
	r=j%BASE;
	B[i][c]|=(1<<r);
	G[i].push_back(j);
}
int NrBiti(uint n)
{
	return HalfBits[n&MASK]+HalfBits[n>>(BASE>>1)];
}
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);

    long long 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<=(N/BASE);++j)
			sol+=NrBiti(B[i][j]&B[*it][j]);
	fout<<sol/6;
	return 0;
}