Cod sursa(job #325211)

Utilizator TabaraTabara Mihai Tabara Data 19 iunie 2009 15:14:35
Problema Triplete Scor 90
Compilator c Status done
Runda Arhiva de probleme Marime 1.15 kb
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define in "triplete.in"
#define out "triplete.out"

#define MASK (0x80)
#define MMAX (1<<16)
#define BYTEMAX 257

typedef struct set {
	char *f;
} *PSet, Set;

PSet L;

void Add ( int i, int j )
{
	unsigned char a = MASK;
	int C, R;
	C = (j>>3);
	R = j - (C<<3);
	a >>= R;
	L[i].f[C] |= a;
}

int q[2*MMAX+3][2], ind, N, M;
int nrsol;
int cnt[BYTEMAX];

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

	unsigned char a;
	int i, j, k, l;
	
	for ( i = 1; i < BYTEMAX-1; ++i )
		cnt[i] = cnt[i>>1] + (i&1);
	
	scanf ( "%d%d", &N, &M );
	L = (PSet)calloc ( N+1,sizeof(Set) );
	for ( i = 1; i <= N; ++i )
		L[i].f = (char*)calloc ( (N>>3), sizeof(char) );
	
	for ( ; M > 0; --M )
	{
		scanf ( "%d%d", &i, &j );
		Add ( i, j );
		Add ( j, i );
		q[++ind][0] = i; q[ind][1] = j;
		q[++ind][0] = j; q[ind][1] = i;
	}

	for ( k = 1; k <= ind; ++k  )
	{	
		i = q[k][0];
		j = q[k][1];
		for ( l = 0; l <= (N>>3); ++l )
		{
			 a = ((L[i].f[l]) & (L[j].f[l]));
			 nrsol += cnt[a];
		}
	}

	printf ( "%d\n", nrsol/6 );
	for ( i = 1; i <= N; ++i )
		free ( L[i].f );
	free ( L );
	return 0;
}