Pagini recente » Cod sursa (job #189781) | Cod sursa (job #1357662) | Cod sursa (job #2512256) | Cod sursa (job #208926) | Cod sursa (job #36777)
Cod sursa(job #36777)
//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;
}