Cod sursa(job #20191)

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

using namespace std;

const int B = 20;
const int maxn = 5097;
const int nel =  maxn / B + 3;


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

int lsb ( int x )
{
    return ( (x-1)^x )&x;
}

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];
		while ( leg[ maxn + 1 ][j] )
		{
		    leg[ maxn + 1 ][ j ] -= lsb( leg[ maxn + 1 ][ j ] );
		    ntrip++;
		}
	    }
	}
	
	printf("%d\n", ntrip/3);

	fclose(stdin);
	fclose(stdout);

	return 0;
}