Cod sursa(job #1473993)

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

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

typedef struct {
  int u, v;
} cell;

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

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

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

int main(void) {
  int 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.
  int 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;
}