Cod sursa(job #7027)

Utilizator marius_902002Cocis Marius Gabriel marius_902002 Data 21 ianuarie 2007 11:54:59
Problema Triplete Scor 0
Compilator cpp Status done
Runda preONI 2007, Runda 1, Clasa a 10-a Marime 0.95 kb
#include<stdio.h>

long i,j,m,n,trip,k;

typedef struct{
	long s,d;
}e;
e s[1001],aux;

long divide(int p,int q);
void qsort(int p,int q);

int main(){
freopen("triplete.in","r",stdin);
freopen("triplete.out","w",stdout);

scanf("%ld%ld",&n,&m);

for(i=1;i<=m;i++)
	scanf("%ld%ld",&s[i].s,&s[i].d);

qsort(1,m);
for(i=1;i<m;i++)
	for(j=i+1;j<=m;j++)
		if(s[i].s==s[j].s)
		{
			for(k=1;k<=m;k++)
				if((s[i].d==s[k].s&&s[j].d==s[k].d)||(s[i].d==s[k].d&&s[j].d==s[k].s)){
					trip++;
					break;
				}
		}

printf("%ld",trip);
return 0;
}
long divide(int p,int q)
{
	long st=p,dr=q,x=s[p].s;
	while(st<dr)
	{
		while(st<dr && s[dr].s>=x)
			dr--;

		aux=s[dr];
		s[dr]=s[st];
		s[st]=aux;
		while(st<dr &&s[st].s<=x)
			st++;

		aux=s[st];
		s[st]=s[dr];
		s[dr]=aux;
	}
	s[st].s=x;
	return st;


}
void qsort(int p,int q)
{
	long m=divide(p,q);
	if(m-1>p)
		qsort(p,m-1);
	if(m+1<q)
		qsort(m+1,q);
}