Cod sursa(job #28064)

Utilizator AdixSuciu Adrian Adix Data 7 martie 2007 14:30:00
Problema Triplete Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.23 kb
#include <stdio.h>
#include <math.h>
long m,n;
unsigned long solutie;
int muc[65537][2];
unsigned long mat[4098];

void citire(){
		 FILE *in;
		 long i,x,y;
		 in=fopen("triplete.in","r");
		 fscanf(in,"%ld %ld",&n,&m);

		 for(i=1;i<=m;i++){
			 fscanf(in,"%ld %ld",&x,&y);
			 muc[i][0]=x;muc[i][1]=y;
			 mat[x]+=pow(2,y);
			 mat[y]+=pow(2,x);
											 }
		 fclose(in);
		 }


long formula(long k,long l){

long x,i,j;
x=mat[k]&mat[l];
i=n;j=0;
while(x!=0){

if((x-pow(2,i))>=0){ j++;x=x-pow(2,i);}
i--;
}
return j;

}

void procesare(){
long i,k,l;
/*
Pentru o muchie fixata este suficienta iterarea prin lista de adiacenta a
nodurilor a si b si adunarea la numarul total de solutii a numarului de
noduri comune. Acest algoritm are complexitatea O(M * N),
pentru ca parcurgerea unei liste de adiacenta se realizeaza in O(N)
*/
for(i=1;i<=m;i++){
//		for(j=1;j<=n;j++){
	//	if(j==muc[i][0]||j==muc[i][1]) continue;
		k=muc[i][0];
		l=muc[i][1];
						solutie+=formula(k,l);
						}
}
void scriere(){
		 FILE *out;
		 out=fopen("triplete.out","w");
		 fprintf(out,"%ld",solutie/3);
		 fclose(out);
     }

int main(){
     citire();
    procesare();
     scriere();
     return 0;
     }