Cod sursa(job #1718265)

Utilizator rocandu16Badulescu Dan Andrei rocandu16 Data 17 iunie 2016 10:16:54
Problema Triplete Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.75 kb
#include <stdio.h>
#define MAXG 256
#define MAXN 4096
#define MAXM 65536
int ma[MAXN][MAXG], x[MAXM], y[MAXM];
int nrb[(1 << 16)];

void precalc(){
  int i;
  for(i = 1; i < (1 << 16); i++)
    nrb[i] = nrb[i / 2] + (i & 1);
}

int main(){
  precalc();
  FILE *fin,*fout;
  fin = fopen("triplete.in", "r");
  fout= fopen("triplete.out","w");
  int n, m, i, j, g;
  fscanf(fin, "%d%d", &n, &m);
  g = (n - 1) / 16;
  for(i = 0; i < m; i++){
    fscanf(fin, "%d%d", &x[i], &y[i]);
    x[i]--;  y[i]--;
    ma[x[i]][y[i] / 16] |= (1 << (y[i] % 16));
    ma[y[i]][x[i] / 16] |= (1 << (x[i] % 16));
  }
  int rez = 0;
  for(i = 0; i < m; i++){
    for(j = 0; j <= g; j++){
      rez += nrb[ma[x[i]][j] & ma[y[i]][j]];
    }
  }
  fprintf(fout, "%d", rez / 3);
  return 0;
}