Cod sursa(job #88255)

Utilizator marius135Dumitran Adrian Marius marius135 Data 1 octombrie 2007 01:01:49
Problema Triplete Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.32 kb
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

#define maxm 65536*2+4
#define maxn 4100

long v[maxm],next[maxm],first[maxn],t[maxm];
long list[maxn],nr[maxn],start[maxn];
long ok[maxn];
int sort (const void *a,const void *b)
{
	return *(long  *)a - *(long *)b;
}
long calc(long a,long b)
{
	long i,val =0;
	long x = start[a],y = start[b];
	for(i=x;i<x+nr[a];i++)
		if(t[i] > b) 
			ok[t[i]]++;
	for(i=y;i<y+nr[b];i++)
		if(t[i] > b) 
			if(ok[t[i]]) val++;
	for(i=x;i<x+nr[a];i++)
		if(t[i] > b) 
			ok[t[i]]--;
	return val;
}

int main()
{
	freopen("triplete.in","r",stdin);
	freopen("triplete.out","w",stdout);
	
	long i,n,m,a,b,last;
	
	scanf("%ld %ld",&n,&m);
	
	for(i=1;i<=m;i++)
	{
		scanf("%ld %ld",&a,&b);
		v[i*2-1] = a;
		v[i*2] = b;
		next[i*2] = first[a];
		next[i*2-1] = first[b];
		first[a] = i*2;
		first[b] = i*2-1;
	}
	last = 0;
	
	for(i=1;i<=n;i++)
	{
		long poz = 0,x;
		memset(list,0,sizeof(list));
		x = first[i];
		while(x)
		{
			list[++poz] = v[x];
			x = next[x];
		}
		qsort(list+1,poz,sizeof(list[0]),sort);
		start[i] = last+1;
		nr[i] = poz;
		for(long ii=1;ii<=poz;ii++)
			t[++last] = list[ii];
	}
	//__int64 s=0;
	long long s =0;
	for(i=1;i<=n;i++)
		for(long j=i+1;j<=n;j++)
			s+=calc(i,j);
	printf("%Ld\n",s);
	
	return 0;
}