Cod sursa(job #36777)

Utilizator pitradaPit-Rada Ionel-Vasile pitrada Data 24 martie 2007 00:46:11
Problema Triplete Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.72 kb
//triplete de animale
#include<fstream>
#include<stdlib.h>
using namespace std;

long l,k,m,n,nrtr,i,j,p[4097];
fstream g,h;

struct pereche
	{
	int u,v;
	};

pereche x[65536],aux;

//comparare pereche cu pereche

int f(pereche a,pereche b)
{
if(a.u<b.u) return -1;
if(a.u>b.u) return +1;
if(a.v<b.v) return -1;
if(a.v>b.v) return +1;
return 0;
}

//comparare pereche cu int

int f2(pereche a,int b)
{
if(a.v<b) return -1;
if(a.v>b) return +1;
return 0;
}

//selectare

void selectare(int p,int r,int &q)
{
int i,j,di,dj;
i=p;
j=r;
di=1;
dj=0;
while(i<j)
	{
		if(f(x[i],x[j])>0)
				{
					aux=x[i];
					x[i]=x[j];
					x[j]=aux;
					di=1+di;
					dj=1-dj;
				}
		i=i+di;
		j=j-dj;
	}
q=i;
}

//quicksort

void qsort(int p,int r)
{
int q;
if(p<r)
	{
	selectare(p,r,q);
	qsort(p,q-1);
	qsort(q+1,r);
	}
}


//cautare binara

int cautare(int v,int k)
{
long c,r,q,w;
c=p[v];
r=p[v+1]-1;
w=0;

while((c<=r)&&(w==0))
	{
	q=(c+r)/2;
	if(f2(x[q],k)==0)
		w=q;
		else if(f2(x[q],k)>0)
				c=q+1;
				else r=q-1;
	}
if(w==0) return -1;
	else return w;
}

//program

int main(void)
{
long i,u,v;
g.open("triplete.in",ios::in);
h.open("triplete.out",ios::out);

g>>n>>m;
for(i=1;i<=m;i++)
	{
	g>>u>>v;
	if(u<v)
		{
		x[i].u=u;
		x[i].v=v;
		}
		else {
			x[i].u=v;
			x[i].v=u;
			}
	}

qsort(1,m);

p[1]=1;
k=1;
i=1;
while(i<=m)
	{
	while((i<=m)&&(x[i].u==k))
		i++;
	k++;
	p[k]=i;
	}
for(i=k+1;i<=n+1;i++)
	p[i]=m+1;

for(i=1;i<=n-2;i++)
	for (l=p[i];l<p[i+1];l++)
		{
		v=x[l].v;
		for(j=p[l];j<=p[l+1]-1;j++)
			{
			k=x[j].v;
			if(cautare(v,k)>0) nrtr++;
			}
		}
h<<nrtr;
g.close();
h.close();
return 0;
}