Cod sursa(job #1473998)

Utilizator stoianmihailStoian Mihail stoianmihail Data 20 august 2015 17:37:15
Problema Triplete Scor 0
Compilator c Status done
Runda Arhiva de probleme Marime 1.18 kb
#include <stdio.h>

#define Smerenie 65537
#define Nadejde 4097
#define MASK 31

#define u32 unsigned int

typedef struct {
  u32 u, v;
} cell;

u32 N, M;
cell edge[Smerenie];            /// prieteniile
u32 set[Nadejde][Nadejde >> 5]; /// bitset-ul nostru.

/** Seteaza bitul de pe linia "u", pozitia "v", pe "1". **/
void setBit(u32 u, u32 v) {
  set[u][v >> 5] |= (1 << (v & MASK));
}

/** Numara cati biti are numarul "u". **/
int cBits(u32 u) {
  u32 count = 0;
  while (u) {
    u &= u - 1;
    count++;
  }
  return count;
}

int main(void) {
  u32 i, j;
  FILE *f = fopen("triplete.in", "r");

  /// Citeste relatiile de prietenie.
  fscanf(f, "%d %d", &N, &M);
  for (i = 1; i <= M; i++) {
    fscanf(f, "%d %d", &edge[i].u, &edge[i].v);
    setBit(edge[i].u, edge[i].v);
  }
  fclose(f);

  f = fopen("triplete.out", "w");

  /// Calculeaza numarul de triplete.
  u32 result = 0, groups = (N >> 5);
  for (i = 1; i <= M; i++) {
    for (j = 0; j <= groups; j++) {
      result += cBits(set[edge[i].u][j] & set[edge[i].v][j]);
    }
  }
  fprintf(f, "%d\n", result);
  fclose(f);

  /// Multumim Doamne!
  puts("Doamne ajuta!");
  return 0;
}