Cod sursa(job #1587073)

Utilizator BLz0rDospra Cristian BLz0r Data 1 februarie 2016 19:51:19
Problema Triplete Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.06 kb
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;

#define Nmax 4100
#define Mmax 65540
#define Bmax 64

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

typedef unsigned long long ULL;

ULL v[Nmax][Bmax];
pair < int, int > E[Mmax];

void Addbit ( int x, int y ){

    int Bucket = Bmax - (y / 64) - 1;
    int Bit = y % 64;

    v[x][Bucket] |= ( 1LL << Bit );

    return;
}

int NrBits ( ULL x ){
    return __builtin_popcountll (x);
}

long long Combine ( int x, int y ){

    long long rez = 0;
    for ( int i = 0; i < Bmax; ++i )
        rez += NrBits( v[x][i] & v[y][i] );

    return rez;
}

int main(){

    int N, M, x, y;

    fin >> N >> M;

    for ( int i = 1; i <= M; ++i ){
        fin >> x >> y;
        x--; y--;

        E[i] = make_pair(x,y);

        Addbit ( x, y );
        Addbit ( y, x );
    }

    long long Sol = 0;

    for ( int i = 1; i <= M; ++i )
        Sol += Combine ( E[i].first, E[i].second );

    fout << Sol / 3;

    return 0;
}