Cod sursa(job #20178)

Utilizator webspiderDumitru Bogdan webspider Data 20 februarie 2007 20:05:28
Problema Triplete Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.98 kb
#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;

const int B = 30;
const int maxn = 4096;
const int nel =  maxn / B + 2;


int muchii[65537][2];
int leg[maxn+2][nel];


int n,m;
int ntrip;

int main()
{
	int i,a,b,j,k;
	freopen("triplete.in","r",stdin);
	freopen("triplete.out","w",stdout);

	scanf("%d %d\n", &n, &m);

	for ( i = 0; i < m; i++ )
	{
		scanf("%d %d\n", &a, &b);
		
		muchii[i][0] = a;
		muchii[i][1] = b;
		if ( b % B == 0 )
		    leg[a][ b/B - 1 ] += ( 1 << B );
		else
		    leg[a][ b/B + 1] += ( 1 << (b%B) );
		if ( a % B == 0 )
		    leg[b][ a/B - 1 ] += ( 1 << B );
		else
		    leg[b][ a/B + 1] += ( 1 << (a%B) );
		
	}
	for ( i = 0; i < m; i++ )
	{
	    for ( j = 1; j <= n/B+1; j++ )
	    {
		leg[ maxn + 1 ][j] = leg[ muchii[i][0] ][j] & leg[ muchii[i][1] ][j];
		for ( k = 1; k <= B; k++ )
		    if ( leg[ maxn + 1 ][j] & ( 1<<k ) ) ntrip++;
	    }
	}
	
	printf("%d\n", ntrip/3);

	fclose(stdin);
	fclose(stdout);

	return 0;
}