Cod sursa(job #1244563)

Utilizator tudi98Cozma Tudor tudi98 Data 17 octombrie 2014 19:46:22
Problema Triplete Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.84 kb
#include <fstream>
using namespace std;
#define dim1 67000
#define dim 5000
#define BY 30

int a[dim1],b[dim1];
int d[dim][dim / BY + 5];

inline int get_one(int x){    //numarul bitilor de 1 din reprezentarea binara a lui x 
	int Ret = 0;
	while(x){
	 	Ret++;
	 	x = x & (x-1);
	}
	return Ret;
}

int main(){
    
    ifstream fin("triplete.in");
    ofstream fout("triplete.out");

    int n,m;
	fin >> n >> m;
	for(int i = 1; i <= m; i++){
		fin >> a[i] >> b[i];
		d[a[i]][b[i] / BY] |= 1 << (b[i] % BY);  //bitul care ii corespunde lui b[i] devine 1
		d[b[i]][a[i] / BY] |= 1 << (a[i] % BY);  //bitul care ii corespunde lui b[i] devine 1 		
	}

	int ans = 0;
	for(int i = 1; i <= m; i++){
	 	for(int j = 0; j <= n / BY; j++){
	 		ans += get_one(d[a[i]][j] & d[b[i]][j]); 	
	 	}
	}
	ans /= 3;
	fout << ans << "\n";

}