Cod sursa(job #402756)

Utilizator vlad.doruIon Vlad-Doru vlad.doru Data 24 februarie 2010 09:35:07
Problema Triplete Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.91 kb
#include <fstream>

using namespace std;

ifstream in("triplete.in");
ofstream out("triplete.out");

const int N=1<<12;
const int B=8;
const int M=1<<16;
unsigned int a[N][N>>6];
unsigned int n,m;

struct muchie{
	int x,y;
};
muchie v[M];

inline unsigned int componenta(unsigned int x){
	return x>>6;
}

inline unsigned int bit(unsigned int x){
	return x & 63;
}
 
void citire(){
	in>>n>>m;
	for(unsigned int i=0;i<m;++i){
		in>>v[i].x>>v[i].y;
		--v[i].x;
		--v[i].y;
		a[v[i].x][componenta(v[i].y)]|=1<<bit(v[i].y);
		a[v[i].y][componenta(v[i].x)]|=1<<bit(v[i].x);
	}
}

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

int main(){
	citire();
	unsigned int i,j,k=m>>6;
	long long s=0;
	for(i=0;i<m;++i){
		for(j=0;j<=k;j++){
			s+=nrbiti(a[v[i].x][j]&a[v[i].y][j]);
		}
	}
	out<<s/3<<"\n";
	in.close();
	out.close();
	return 0;
}