Cod sursa(job #1547635)

Utilizator tamionvTamio Vesa Nakajima tamionv Data 9 decembrie 2015 18:10:47
Problema Triplete Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.94 kb
#include <fstream>
#include <array>
#include <utility>
#include <vector>
using namespace std;

template <int maxn>
class my_bitset{
	array<uint64_t, maxn/64> buf = {};
public:
	my_bitset(): buf({}){}
	void set(const int poz){
		buf[poz>>6] |= 1<<(poz&63); }
	unsigned long long operator&(const my_bitset<maxn>& rhs)const{
		unsigned long long rez = 0;
		for(int i = 0, lim = maxn/64; i < lim; ++i){
			rez += __builtin_popcountll(buf[i] & rhs.buf[i]); }
		return rez; } };

constexpr int maxn = 4096;

int main(){
	ifstream f("triplete.in");
	ofstream g("triplete.out");

	int n, m;
	f >> n >> m;

	vector<my_bitset<maxn>> v(n);
	vector<pair<int, int>> mucs(m);

	for(auto& x : mucs){
		f >> x.first >> x.second;
		--x.first, --x.second;
		v[x.first].set(x.second);
		v[x.second].set(x.first); }
	unsigned long long rez = 0;
	for(const auto x : mucs){
		rez += v[x.first] & v[x.second]; }
	g << rez/3ull;
	return 0; }