Cod sursa(job #840619)

Utilizator stoicatheoFlirk Navok stoicatheo Data 22 decembrie 2012 22:15:51
Problema Triplete Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.98 kb
#include <fstream>
#include <iostream>
#include <bitset>
 
using namespace std;
 
#define nmax 4100
#define nrmax (1<<20)
#define mmax 65537
 
ifstream f("triplete.in");
ofstream g("triplete.out");
 
int n, m;
int a[nmax][nmax/20 + 1];
int nr[((1<<20)+1)];
int A[mmax], B[mmax];
 
void citeste(){
 
    f >> n >> m;
    for(int i=1; i<=m; i++){
        int x, y;
        f >> x >> y;
        a[x][y/20] |= (1<<(y % 20));
        a[y][x/20] |= (1<<(x % 20));
        A[i] = x;
        B[i] = y;
    }
 
}
 
void rezolva(){
 
    int cnt = 0;
 
    
    for(int i=1; i<=nrmax; i++)
        nr[i] = nr[i/2] + (i%2);
 
 
    for(int i=1; i<=m; i++){
        int x = A[i];
        int y = B[i];
        for(int j=0; j<=n/20; 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;
 
}