Pagini recente » Cod sursa (job #2235561) | Cod sursa (job #220918) | Cod sursa (job #2150964) | Cod sursa (job #50469) | Cod sursa (job #1520796)
#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;
}