Cod sursa(job #1587082)

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

#define Nmax 4096
#define Mmax 65537
#define Bmax 64

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

typedef unsigned long long ULL;

ULL v[Nmax][Bmax-1];
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;
}

string Buffer;
string :: iterator it;

int ReadInt(){

    int nr = 0;

    while ( *it < '0' || *it > '9' )
        it++;

    while ( *it >= '0' && *it <= '9' ){
        nr = nr * 10 + ( *it - '0' );
        it++;
    }

    return nr;
}

int main(){

    int N, M, x, y;

    getline( fin, Buffer, (char)0 );
    it = Buffer.begin();

    N = ReadInt();
    M = ReadInt();

    for ( int i = 1; i <= M; ++i ){

        x = ReadInt() - 1;
        y = ReadInt() - 1;

        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;
}