Cod sursa(job #1520796)

Utilizator bciobanuBogdan Ciobanu bciobanu Data 9 noiembrie 2015 14:51:27
Problema Triplete Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.32 kb
#include <fstream>
#include <algorithm>

using namespace std;

const int MAX_N = 4096;
const int BITS = 16;
const int MASK = (1 << BITS) - 1;

unsigned long long mat[MAX_N][(MAX_N >> 6) + 1];
unsigned char popCount[1 << BITS];

inline int popCntLL(const unsigned long long A) {
    return popCount[A & MASK]
            + popCount[(A >> 16) & MASK]
            + popCount[(A >> 32) & MASK]
            + popCount[(A >> 48) & MASK];
}

int main(void) {
    ifstream in("triplete.in");
    ofstream out("triplete.out");
    in.tie(0);
    ios_base::sync_with_stdio(0);
    int n, m, u, v;

    in >> n >> m;

    for (int i = 0; i < m; i++) {
        auto setBit = [&] (const int &u, const int &v) -> void {
            mat[u][v >> 6] |= (1ULL << (v & 63));
        };
        in >> u >> v;
        if (u > v) {
            swap(u, v);
        }
        setBit(u - 1, v - 1);
    }

    in.seekg(0);
    in >> n >> m;

    for (int i = 1; i < (1 << BITS); i++) {
        popCount[i] = (i & 1) + popCount[i >> 1];
    }

    int q = 0;
    for (int i = 0; i < m; i++) {
        int u, v;
        in >> u >> v;
        u--; v--;
        for (int j = 0; (j << 6) <= n; j++) {
            q += popCntLL(mat[u][j] & mat[v][j]);
        }
    }

    out << q << '\n';
    out.close();
    return 0;
}