Cod sursa(job #589029)

Utilizator valentin.harsanValentin Harsan valentin.harsan Data 10 mai 2011 17:25:44
Problema Triplete Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.8 kb
#include<stdio.h>

unsigned int n,m,a[4096][130],x[65540][2];

int nrbiti(int n) {
	int nr=0;
	while(n!=0) {
		++nr;
		n&=(n-1);
	}
	return nr;
}

int main() {
	int i,j,b,s=0,k,xx,yy;
	freopen("triplete.in","r",stdin);
	freopen("triplete.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(i=1;i<=m;++i) {
		scanf("%d%d",&x[i][0],&x[i][1]);
		a[x[i][0]][x[i][1]>>5]|=(1<<(x[i][1]&31));
		a[x[i][1]][x[i][0]>>5]|=(1<<(x[i][0]&31));
	}
	/*for(i=1;i<=n;++i) {
		for(j=1;j<=n;++j) {
			if((a[i][j>>5]&1<<(j&31))!=0)
				printf("1 ");
			else
				printf("0 ");
		}
		printf("\n");
	}*/
	for(xx=1;xx<=n;++xx) {
		for(yy=xx+1;yy<=n;++yy)
			if((a[xx][yy>>5] & (1<<(yy&31)))!=0)
				for(j=0;j<=n>>5;++j) {
					b=(a[xx][j]&a[yy][j]);
					s+=nrbiti(b);
				}
	}
	printf("%d",s/3);
	return 0;
}