Cod sursa(job #402800)

Utilizator vlad.doruIon Vlad-Doru vlad.doru Data 24 februarie 2010 10:19:03
Problema Triplete Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.96 kb
#include <fstream>
#include <vector>

using namespace std;

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

const int N=1<<13;
const int B=8;
const int M=1<<17;
vector <unsigned int> adj[1<<17];
unsigned char a[N][N>>3];
unsigned int n,m;

inline unsigned int comp(unsigned int x){
	return x>>3;
}

inline unsigned int bit(unsigned int x){
	return x & 7;
}
 
void citire(){
	int x,y;
	in>>n>>m;
	for(unsigned int i=0;i<m;++i){
		in>>x>>y;
		adj[x].push_back(y);
		//adj[y].push_back(x);
		a[x][comp(y)]|=(1<<bit(y));
		a[y][comp(x)]|=(1<<bit(x));
	}
}

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

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