Cod sursa(job #1657096)

Utilizator hrazvanHarsan Razvan hrazvan Data 20 martie 2016 09:53:49
Problema Triplete Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 0.86 kb
#include <stdio.h>
#define MAXG 256
#define MAXN 4096
#define MAXM 65536
#define SHIFT 16
int ma[MAXN][MAXG], x[MAXM], y[MAXM];
int nrb[(1 << SHIFT)];

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

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