Cod sursa(job #1718263)

Utilizator matericristea88Cristea-Enache Matei matericristea88 Data 17 iunie 2016 10:12:26
Problema Triplete Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.18 kb
#include <cstdio>

#define Nmax 65537
#define N2 4097
#define MASK 31

typedef struct {
  unsigned int u, v;
} cell;

unsigned int N, M;
cell edge[Nmax];            // prieteniile
unsigned int set[N2][N2 >> 5]; // bitset-ul nostru.

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

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

int main() {
  unsigned int i, j;
  freopen("triplete.in","r",stdin);
  freopen("triplete.out","w",stdout);
  // Citeste relatiile de prietenie.
  scanf("%d %d", &N, &M);
  for (i = 1; i <= M; i++) {
    scanf("%d %d", &edge[i].u, &edge[i].v);
    if (edge[i].u > edge[i].v) {
      unsigned int tmp = edge[i].u;
      edge[i].u = edge[i].v;
      edge[i].v = tmp;
    }
    setBit(edge[i].u, edge[i].v);
  }
  // Calculeaza numarul de triplete.
  unsigned 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]);
    }
  }
  printf("%d\n", result);
  return 0;
}