Cod sursa(job #22555)

Utilizator Spike7d5Spike7d5 Spike7d5 Data 26 februarie 2007 20:04:10
Problema Triplete Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.13 kb
#include <stdio.h>
#include <string.h>
#define N 2000
#define M 2000

int a[M], b[M], x[M], y[M];

void sort(int l, int r);

int main () {
int n, m, i, j, k, d[N][N], p[N], q, t;

freopen ("triplete.in", "rt", stdin);
freopen ("triplete.out", "wt", stdout);

scanf ("%d%d", &n, &m);
memset (d, 0, sizeof(int)*N*N);

for (i=0;i<m;i++) {
  scanf ("%d%d", &q, &t);
  d[q][t]=d[t][q]=1;
  x[i*2]=q; y[i*2]=t;
  x[i*2+1]=t; y[i*2+1]=q; }

m=2*m;
x[m]=n+1; y[m]=n+1;
sort (0, m);

p[0]=p[1]=0;
for (i=1;x[i]<=n;i++)
  if (x[i]!=x[i+1])
    p[x[i+1]]=i+1;

t=0;
for (i=1;i<=n;i++)
  for (j=p[i];x[p[i]]==x[j];j++)
    for (k=p[y[j]];x[p[y[j]]]==x[k];k++)
      if (d[i][y[k]]==1)
	t++;

printf ("%d\n", t/6);

return 0;
}



void sort(int l, int r) {
int c, i, j, k;
if (l==r) return;
c=(l+r)/2;
sort(l, c);
sort(c+1, r);

i=l; j=c+1; k=l;
while (i<=c && j<=r)
  if (x[i]<x[j]) {
    b[k]=y[i];
    a[k++]=x[i++]; }
  else {
    b[k]=y[j];
    a[k++]=x[j++]; }

while (i<=c) { b[k]=y[i]; a[k++]=x[i++]; }
while (j<=r) { b[k]=y[j]; a[k++]=x[j++]; }

for (k=l; k<=r; k++) { x[k]=a[k]; y[k]=b[k]; }
}