Cod sursa(job #80586)

Utilizator MarcvsHdrMihai Leonte MarcvsHdr Data 28 august 2007 18:22:00
Problema Triplete Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.17 kb
# include <stdio.h>

const long int NRBITI=30;
const long int MAXN=4096/NRBITI;
const long int MAXX=4096;
const long int MAXM=100000;
const long int MAXC=16;

long int a[MAXX+4][MAXN+4],n,m;
long long int sol;
long int nbiti[MAXM+1];

void init(){
for (long int i=1;i<=(long int)1<<MAXC;i++) nbiti[i]=1+nbiti[i&(i-1)];
}

long int nrbiti(long int a)
{
if (a<1<<16) return nbiti[a];
return nbiti[a>>15]+nbiti[a&(((long int)1<<15)-1)];
}

void add(long int loc,long int inf)
{
long int adaos=0;
if (inf%NRBITI==0) adaos=1;
a[loc][inf/NRBITI+1-adaos]|=(long int)1<<(inf%NRBITI);
}

void citire()
{
long int aa,bb;
FILE *f=fopen("triplete.in","r");
fscanf(f,"%ld%ld",&n,&m);
long int i;
for (i=1;i<=m;i++)
	{
	fscanf(f,"%ld%ld",&aa,&bb);
	add(aa,bb);
	add(bb,aa);
	}
fclose(f);
}

void calculeaza()
{
FILE *f=fopen("triplete.in","r");
fscanf(f,"%ld%ld",&n,&m);
long int i,aa,bb,j;
for (i=1;i<=m;i++)
	{
	fscanf(f,"%ld%ld",&aa,&bb);
	for (j=1;j<=n/NRBITI+1;j++)
		sol+=nrbiti(a[aa][j]&a[bb][j]);
	}
FILE *g=fopen("triplete.out","w");
fprintf(g,"%lld\n",sol/3);
fcloseall();
}

int main()
{
citire();
init();
calculeaza();
return 0;
}