Cod sursa(job #20133)

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

using namespace std;

const int modn = 49999;
const int bzh  = 17;

vector<int> fii[4097];
vector<int> stuff;
int muchii[65537][2];
int intln[4097];

int hash[49999];

int n,m;
int ntrip;

int bs( int ident, int val )
{
    int N = fii[ ident ].size();
    int step;
    int i;
    
    for ( step = 1; step <= N; step <<= 1 );
    for ( i = -1; step; step >>=1 )
    if ( i + step < N )
	if ( fii[ ident ][ i + step ] <= val )
	    i += step;
    if ( fii[ ident ][ i ] == val ) return 1;
    return 0;
}

int main()
{
	int i,a,b,j;
	int hsh;
	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);
		fii[a].push_back(b);
		fii[b].push_back(a);
		muchii[i][0] = a;
		muchii[i][1] = b;
	}
	for ( i = 1 ; i <= n ; i++ )
		sort( fii[i].begin(), fii[i].end() );
	for ( i = 0; i < m; i++ )
	{
		
		for ( j = 0; j < fii[ muchii[i][0] ].size(); j++ )
		{
			if ( bs( muchii[i][1], fii[ muchii[i][0] ][j] ) )
			{/*
				stuff.clear();
				stuff.push_back( muchii[i][0] );
				stuff.push_back( muchii[i][1] );
				stuff.push_back( fii[ muchii[i][0] ][j] );

				sort( stuff.begin(), stuff.end() );
				
				hsh = ( (bzh*bzh*stuff[0] ) % modn + ( bzh*stuff[1] ) % modn + stuff[2] ) % modn;
				
				if ( !hash[ hsh ] )
				{*/
					ntrip++;
				/*	hash[ hsh ] = 1;
				}*/
				
			}
		}
	}
	
	printf("%d\n", ntrip/3);

	fclose(stdin);
	fclose(stdout);

	return 0;
}