Cod sursa(job #1547630)

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

template <int maxn>
class my_bitset{
	array<uint32_t, maxn/32> buf = {};
public:
	my_bitset(): buf({}){}
	void set(const int poz){
		buf[poz>>5] |= 1<<(poz&31); }
	unsigned long long operator&(const my_bitset<maxn>& rhs)const{
		unsigned long long rez = 0;
		for(int i = 0, lim = maxn/32; i < lim; ++i){
			rez += __builtin_popcount(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; }