Cod sursa(job #1439098)

Utilizator depevladVlad Dumitru-Popescu depevlad Data 21 mai 2015 14:10:32
Problema Triplete Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.08 kb
#include <fstream>

using namespace std;

const char inFile[] = "triplete.in";
const char outFile[] = "triplete.out";
const int MAX_N = 4096;
const int MAX_M = 65536;
const int LLU_SIZE = 64;
const int NR_GROUPS = MAX_N / LLU_SIZE + 1;

ifstream in(inFile);
ofstream out(outFile);

struct Edge {
    int node1;
    int node2;
};

unsigned long long Adj[MAX_N][NR_GROUPS];
Edge E[MAX_M];

inline int getBits(unsigned long long X) {
    int nBits = 0;
    while(X) {
        nBits++;
        X &= (X-1);
    }
    return nBits;
}

int main() {
    int n, m, k, i, j, ans = 0;

    in >> n >> m;
    for(i = 0; i < m; i++) {
        in >> E[i].node1 >> E[i].node2;
        E[i].node1--;
        E[i].node2--;
        Adj[E[i].node1][E[i].node2 / LLU_SIZE] |= (1ll << (E[i].node2 % LLU_SIZE));
        Adj[E[i].node2][E[i].node1 / LLU_SIZE] |= (1ll << (E[i].node1 % LLU_SIZE));
    }

    for(i = 0; i < m; i++)
        for(j = 0; j < NR_GROUPS; j++)
            ans += getBits(Adj[E[i].node1][j] & Adj[E[i].node2][j]);

    out << ans / 3;
    return 0;
}