Cod sursa(job #1933829)

Utilizator 1475369147896537415369Andrei Udriste 1475369147896537415369 Data 20 martie 2017 22:46:33
Problema Triplete Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 kb
#include <cstdio>

long long adj[4097][129];
int vertices, edges, answer, x, y;
int nr[65537], u[65537], v[65537];

inline int count(long long x){

    return nr[x >> 16] + nr[x & (65536 - 1)];
}

inline void add(int i, int j){

    adj[i][j / 32] |= 1LL << (j % 32);
}

void Precalculate(){

    for(int i = 1; i <= 65536-1; ++i)
        for(int x = i; x; x >>= 1)
            if(x & 1) nr[i]++;
}

int main(){

    freopen("triplete.in", "r", stdin);
    freopen("triplete.out", "w", stdout);

    Precalculate();

    scanf("%d %d", &vertices, &edges);

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

        scanf("%d %d", &u[i], &v[i]);

        add(u[i], v[i]);
        add(v[i], u[i]);
    }

    for(int i = 1; i <= edges; i++){
        for(int j = 0; j <= vertices / 32; j++)
            answer += count(adj[u[i]][j] & adj[v[i]][j]);
    }

    printf("%d", answer / 3);

    return 0;
}