Cod sursa(job #8244)

Utilizator mockeBarca Cristian Mihai mocke Data 23 ianuarie 2007 23:11:00
Problema Triplete Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.47 kb

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

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

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

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

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

     for (i = 1; i < (1<<17); i++)
       Nr[i] = Nr[(unsigned int)i >> 1] + ((unsigned int)i&1);
}

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

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

	 if (N == 1) { printf("0\n"); return 0; }
     if (N == 2) { printf("0\n"); return 0; }
     if (N == 3 && M != 3) { printf("0\n"); return 0;}
	 if (M == (N-1)*N/2) { printf("%lld\n", (long long)(N-1)*(N-2)*N/6); return 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();
	 
	 rez = 0;
	 
     for (i = 1; i <= M; i++)
     {
          a = (unsigned int)V[i].x;
          b = (unsigned int)V[i].y;

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

               rez += Nr[(unsigned int)cfg & 65535] + Nr[(unsigned int)cfg >> 16];
          }
     }
	 
	 rez = (long long)rez/3;

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

     return 0;
}