Cod sursa(job #8219)

Utilizator mockeBarca Cristian Mihai mocke Data 23 ianuarie 2007 22:38:03
Problema Triplete Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.08 kb

#include <stdio.h>
#define NMAX 4096
#define MMAX 66000

struct per { int x, y; } V[MMAX];

int Nr[1 << 17];
int A[NMAX][ (NMAX/32) + 2];
int i, j, N, M, a, b;
unsigned int cfg;
long long rez;

void set(int cnf, int x)
{
   A[cnf][x>>5] |= 1 << (x & 31);
}

void prep()
{
	int i; 
	
	Nr[0] = 0;

     for (i = 1; i <= (1 << 16); i++)
       Nr[i] = Nr[i >> 1] + (i&1);
}

int main()
{
     freopen("triplete.in","r",stdin);
     freopen("triplete.out","w",stdout);

     scanf("%d %d", &N, &M);

    rez = 0;

     for (i = 1; i <= M; i++)
     {
          scanf("%d %d", &a, &b);

          V[i].x = a;
          V[i].y = b;

          set(a, b);
          set(b, a);
     }

	 prep();
	 
     for (i = 1; i <= M; i++)
     {
          a = V[i].x;
          b = V[i].y;

          for (j = 0; j <= 128; j++)
          {
               cfg = (unsigned int)(A[a][j] & A[b][j]);

               rez += Nr[cfg & ((1<<16) - 1)] + Nr[cfg >> 16];
          }
     }
	 
	 rez = (long long)rez/3;

     printf("%lld\n", rez);

     return 0;
}