Cod sursa(job #1718267)

Utilizator Matei_IgnutaMatei Ignuta Matei_Ignuta Data 17 iunie 2016 10:25:04
Problema Triplete Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.81 kb
#include <stdio.h>

using namespace std;

#define MAXG 256
#define MAXN 4096
#define MAXM 65536

int ma[MAXN][MAXG], x[MAXM], y[MAXM];
int nr[(1 << 16)];

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

int main()
{
    precalc();
    freopen("triplete.in", "r", stdin);
    freopen("triplete.out", "w", stdout);
    int n, m, i, j, g;
    scanf("%d %d", &n, &m);
    g = (n-1)/16;
    for (int i=0; i<m; i++)
        {
        scanf("%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 += nr[ma[x[i]][j] & ma[y[i]][j]];
        }
    }
  printf("%d", rez/3);
  return 0;
}