Cod sursa(job #1547639)

Utilizator tamionvTamio Vesa Nakajima tamionv Data 9 decembrie 2015 18:15:33
Problema Triplete Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.52 kb
#include <fstream>
#include <cstdlib>
#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;

template <int dim>
class parsator{
	ifstream f;
	array<char, dim> buf;
	int poz = dim;
	void refill(){
		if(poz == dim){
			f.read(&buf[0], dim);
			poz = 0; } }
public:
	parsator(const char name[]): f(name){
		refill(); }
	parsator<dim>& operator>>(int& x){
		x = 0;
		for( ; !isdigit(buf[poz]); ){
			++poz;
			refill(); }
		for( ; isdigit(buf[poz]); ){
			x = 10 * x + buf[poz] - '0';
			++poz;
			refill(); }
		return *this; } };
 
int main(){
    parsator<10000> 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; }