Cod sursa(job #1611721)

Utilizator Master011Dragos Martac Master011 Data 24 februarie 2016 13:03:45
Problema Triplete Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.91 kb
#include<cstdio>
using namespace std;

const int nMax = 4096 + 1, mMax = 65536 + 1, base = 32;
int mat[nMax][nMax / base];
int st[mMax], dr[mMax];

int nrB(int x){
    int nr = 0;
    while(x){
        nr++;
        x = x & (x - 1);
    }
    return nr;
}

int main (){

    FILE *in = fopen("triplete.in","r");
    FILE *out = fopen("triplete.out","w");

    int n, m, a;
    fscanf(in,"%d%d", &n, &m);

    for(int i = 1 ; i <= m ; ++i){
        fscanf(in,"%d%d", &st[i], &dr[i]);

        if(st[i] > dr[i]){
            a = st[i];
            st[i] = dr[i];
            dr[i] = a;
        }
        mat[st[i]][dr[i] / base] += 1 << (dr[i] % base);
    }

    int sol = 0, lim = n / base;

    for(int i = 1 ; i <= m ; ++i){
        for(int j = 0 ; j <= lim ; ++j){
            sol += nrB(mat[st[i]][j] & mat[dr[i]][j]);
        }
    }
    fprintf(out,"%d\n", sol);
    return 0;
}