Cod sursa(job #757329)

Utilizator vendettaSalajan Razvan vendetta Data 11 iunie 2012 20:35:51
Problema Triplete Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.02 kb
#include <fstream>
#include <iostream>
#include <bitset>

using namespace std;

#define nmax 4100
#define nrmax (1<<16)
#define cnst 16
ifstream f("triplete.in");
ofstream g("triplete.out");

int n, m;
int a[nmax][nmax/16 + 1];
int nr[((1<<16)+1)];
int A[nmax], B[nmax];

void citeste(){

    f >> n >> m;
    for(int i=1; i<=m; i++){
        int x, y;
        f >> x >> y;
        a[x][y/16] |= (1<<(y % 16));
        a[y][x/16] |= (1<<(x % 16));
        A[i] = x;
        B[i] = y;
    }

}

void rezolva(){

    int cnt = 0;

    //nr[i] = numarul de biti de 1 din reprezentarea binara a lui 'i';
    for(int i=1; i<=nrmax; i++)
        nr[i] = nr[i>>1] + (i&1);


    for(int i=1; i<=m; i++){
        int x = A[i];
        int y = B[i];
        for(int j=0; j<=n/16; j++){
            cnt += nr[(a[x][j]&a[y][j])];
        }
    }

    cout << cnt/3 << "\n";
    g << cnt/3 << "\n";


}

int main(){

    citeste();
    rezolva();

    f.close();
    g.close();

    return 0;

}