Cod sursa(job #324937)

Utilizator TabaraTabara Mihai Tabara Data 18 iunie 2009 02:34:33
Problema Triplete Scor 20
Compilator c Status done
Runda Arhiva de probleme Marime 0.98 kb
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

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

#define NMAX 5000
#define BMAX 513
#define MASK (0x80)
#define MMAX 65537
#define TMAX 257

typedef struct set {
	char set[BMAX];
} Set;

Set S[NMAX];
int N, M, ind, nrsol;
int cnt[MMAX];

struct muchie {
	int v1, v2;
} g[NMAX];

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

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

	int i, j;
	
	for ( i = 1; i <= MMAX; ++i )
		cnt[i] = cnt[i>>1] + (i&1);
	
	scanf ( "%d%d", &N, &M );
	
	for ( ; M > 0; --M )
	{
		scanf ( "%d%d",&i,&j );
		Add ( i, j );
		Add ( j, i );
		g[++ind].v1 = i; g[ind].v2 = j;
	}

	unsigned char a;
	for ( i = 1; i <= ind; ++i )
	{	
		for ( j = 0; j <= (N>>3); ++j )
		{	
			a = (S[g[i].v1].set[j]) & ( S[g[i].v2].set[j] );
			nrsol += cnt[a];
		}
		
	}
		
	printf ( "%d\n", nrsol/3 );
	return 0;
}