Cod sursa(job #264696)

Utilizator BaduBadu Badu Badu Data 22 februarie 2009 16:39:53
Problema Triplete Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.93 kb
#include<stdio.h>
#define btgr 64
#define N 4096

int n,m;
long BIT[N][btgr],triplete;

int bit_count(int a,int b){
	int i,nr,cat=0;
	int gr = n/btgr + 1;

	for(i=1;i<=gr;i++){
		nr = BIT[a][i] & BIT[b][i];

		for(;nr;nr>>=1,cat+=nr&1?1:0);
	}
	return cat;
}
int main(){

	freopen("triplete.in","rt",stdin);
	freopen("triplete.out","wt",stdout);
	int x,y,i,k,j,gr,how,ordine;
	scanf("%d%d",&n,&m);
	for(;m--;){
		scanf("%d%d",&x,&y);
		BIT[x][0]++;
		gr = y/btgr + 1;
		ordine =y%btgr;
		how = 1<<(btgr - ordine);
		BIT[x][gr] ^= how;
	}
	gr = n/btgr + 1;
	for(i=1;i<=n;i++){
	if(BIT[i][0]){
		for(j=1;j<=gr;j++){
			for(k=btgr-1;k>=1;k--){
				if(BIT[i][j] & 1<<k){
					if(j==1) how = btgr - k;
					else how = (j-1)*btgr + btgr - k;
					triplete+=bit_count(i,how);
				}
			}if(j>1) if(BIT[i][j] & 1<<btgr) triplete+=bit_count(i,(j-1)*btgr);
		}
	}

	}


	
	printf("%ld",triplete);			
	return 0;
}