Cod sursa(job #2676289)

Utilizator PatrickCplusplusPatrick Kristian Ondreovici PatrickCplusplus Data 23 noiembrie 2020 21:51:47
Problema Triplete Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.08 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("triplete.in");
ofstream fout("triplete.out");

const int nmax = 4100, b = 60;
int n, mm, m[nmax][nmax];
long long a[nmax][100];
pair <int, int> edge[70000];
int main(){
    fin >> n >> mm;
    for (int i = 1; i <= mm; ++i){
        int x, y;
        fin >> x >> y;
        m[x][y] = m[y][x] = 1;
        edge[i] = {x, y};
    }
    for (int i = 1; i <= n; ++i){
        for (int j = 1; j <= n; j += b){
            for (int k = 0; k < b; ++k){
                if (j + k > n){
                    break;
                }
                if (m[i][j + k])
                    a[i][j / b + 1] |= (1LL << k);
            }
        }
    }
    long long ans = 0;
    for (int i = 1; i <= mm; ++i){
        int nod1 = edge[i].first, nod2 = edge[i].second;
        for (int j = 1; j <= n; j += b){
            long long value = a[nod1][j / b + 1] & a[nod2][j / b + 1];
            ans += __builtin_popcount(value);
        }
    }
    fout << ans / 3 << "\n";
    fin.close();
    fout.close();
    return 0;
}