Cod sursa(job #178681)

Utilizator marinMari n marin Data 14 aprilie 2008 21:59:03
Problema Triplete Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.71 kb
#include <stdio.h>
#define B 16
#define MAXN 4100
#define MAXM 65550


unsigned int v[MAXM],w[MAXM];
unsigned int a[MAXN][MAXN/B+3];
unsigned int cnt[MAXM];

unsigned int n,m,i,j,x,y,s;


int main(){
  FILE *f = fopen("triplete.in","r");
  fscanf(f,"%d %d",&n,&m);

  for(i = 1; i <= 65549; i++)
    cnt[i] = cnt[i>>1]+(i&1);

  for (i=1;i<=m;i++) {
    fscanf(f,"%d %d",&x,&y);
    v[i]=x;
    w[i]=y;
    a[x][y/B]=a[x][y/B]|(1<<(y%B));
    a[y][x/B]=a[y][x/B]|(1<<(x%B));
  }
  fclose(f);
  s=0;
  for (i=1;i<=m;i++)
    for (j=0;j<=n/B+2;j++)
      s+=cnt[(a[v[i]][j]&a[w[i]][j])];
  s=s/3;

  FILE *g = fopen("triplete.out","w");
  fprintf(g,"%d\n",s);
  fclose(f);

  return 0;
}