Cod sursa(job #1551606)

Utilizator alexpetrescuAlexandru Petrescu alexpetrescu Data 16 decembrie 2015 08:41:04
Problema Triplete Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.87 kb
#include <cstdio>
#define MAXM 65536
#define MAXN 4096
#define MASK ((1<<16)-1)
int x[MAXM], y[MAXM], c[1<<16];
long long v[MAXN+1][(MAXN>>6)+2];
int main(){
    int n, m, i, ans, j;
    unsigned long long u;
    FILE *fin, *fout;
    fin=fopen("triplete.in", "r");
    fout=fopen("triplete.out", "w");
    fscanf(fin, "%d%d", &n, &m);
    for(i=0; i<m; i++){
        fscanf(fin, "%d%d", &x[i], &y[i]);
        v[x[i]][y[i]>>6]|=1LL<<(y[i]&63);
        v[y[i]][x[i]>>6]|=1LL<<(x[i]&63);
    }
    for(i=1; i<(1<<16); i++){
        c[i]=1+c[i-(i&(-i))];
    }
    ans=0;
    for(i=0; i<m; i++){
        for(j=0; j<=n>>6; j++){
            u=(unsigned long long)(v[x[i]][j]&v[y[i]][j]);
            ans+=c[u&MASK]+c[(u>>16)&MASK]+c[(u>>32)&MASK]+c[u>>48];
        }
    }
    fprintf(fout, "%d\n", ans/3);
    fclose(fin);
    fclose(fout);
    return 0;
}