Cod sursa(job #2914574)

Utilizator vlad2009Vlad Tutunaru vlad2009 Data 20 iulie 2022 13:15:04
Problema Triplete Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.03 kb
#include <fstream>
#include <vector>
#include <cassert>
#define int long long

using namespace std;

const int MAX_N = 4096;
const int BS = 60;
long long friends[MAX_N + 1][MAX_N / BS + 2];
vector<pair<int, int>> v;
int n, m;

void update(int a, int b) {
    int bucket = 0;
    if (b % BS == 0) {
        bucket = b / BS;
    } else {
        bucket = b / BS + 1;
    }
    int cnt = b - BS * (bucket - 1);
    assert(cnt <= BS);
    friends[a][bucket] |= (1LL << cnt);
}

signed main() {
    ifstream fin("triplete.in");
    ofstream fout("triplete.out");
    fin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int a, b;
        fin >> a >> b;
        v.push_back({a, b});
        update(a, b);
        update(b, a);
    }
    long long answer = 0;
    for (auto it : v) {
        for (int i = 1; i <= MAX_N / BS + 1; i++) {
            long long tmp = (friends[it.first][i] & friends[it.second][i]);
            answer += __builtin_popcount(tmp);
        }
    }
    fout << answer / 3;
    return 0;
}