Cod sursa(job #737574)

Utilizator gabrielvGabriel Vanca gabrielv Data 19 aprilie 2012 18:24:54
Problema Triplete Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.47 kb
using namespace std;
#include<fstream>
#include<bitset>
#include<algorithm>
#include<vector>
#define NMAX 4100
#define go(x,y,v) (v.push_back(make_pair((x),(y))))
#define maxim(a,b) ((a>b)?(a):(b))
//bitset<NMAX> a[NMAX];
//bool a[NMAX][NMAX];
vector< pair <unsigned, unsigned > > M;
vector< unsigned > G[NMAX];
int n,S=0,m;
void citire()
{
	freopen("triplete.in","r",stdin);
	int x,y,i;
	unsigned xx,yy;
	scanf("%d %d",&n,&m);
	for(i=0;i<m;i++)
	{
		scanf("%d %d",&x,&y);
		xx=unsigned(x);
		yy=unsigned(y);
		G[xx].push_back(yy);
		G[yy].push_back(xx);
		//a[x][y]=1;
		//a[y][x]=1;
		go(xx,yy,M);
	}
}
bool search(unsigned val, unsigned i)
{
	/*int left,right,mid;
	left=0;
	right=G[i].size();
	while(left<=right)
	{
		mid=(left+right)/2;
		if(G[i][mid]==val)
			return 1;
		if(G[i][mid]<val)
			left=mid+1;
		else
			right=mid-1;
	}*/
	unsigned j;
	for(j=0;j<G[i].size();j++)
		if(G[i][j]==val)
			return 1;
	return 0;
}
void solve()
{
	unsigned i,j;
	for(i=0;i<(unsigned)m;i++) // parcurgem muchiile
		for(j=0;j<G[M[i].first].size();j++) // cautam in lista de adiacenta a nodului 1 al muchiei
			if(G[M[i].first][j]>maxim(M[i].first,M[i].second))
				if(search(G[M[i].first][j],M[i].second))
				{
					//printf("%hd %hd %hd\n",M[i].first,M[i].second,G[M[i].first][j]);
					S++;
				}
}
void afisare()
{
	freopen("triplete.out","w",stdout);
	printf("%d\n",S);
}
int main()
{
	citire();
	solve();
	afisare();
	return 0;
}