Cod sursa(job #51679)

Utilizator alextheroTandrau Alexandru alexthero Data 16 aprilie 2007 13:55:51
Problema Triplete Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.98 kb
#include <stdio.h>
#include <algorithm>
#include <vector>

#define mmax 65537
#define nmax 4097
#define pb push_back

using namespace std;

vector <int> e[nmax];
const int baza = 30;
int x[mmax],y[mmax],gv[nmax][1000],i,j,n,m,crt,sus,next,tot;

int main() {
	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],&y[i]);
		e[x[i]].pb(y[i]); e[y[i]].pb(x[i]);
	}
	for(i = 1; i <= n; i++) sort(e[i].begin(),e[i].end());

	if(n % baza == 0) sus = n;
	else sus = (n / baza + 1) * baza;
	for(i = 1; i <= n; i++) {
		crt = 0;
		next = 0;
		for(j = 1; j <= sus; j++) {
			crt *= 2;
			if((int)e[i].size() > next && e[i][next] == j) {
				crt++;
				next++;
			}
			if(j % baza == 0) {
				gv[i][++gv[i][0]] = crt;
				crt = 0;
			}
		}
	}
	
	tot = 0;
	for(i = 1; i <= m; i++) {
		for(j = 1; j <= gv[x[i]][0]; j++) 
			tot += __builtin_popcount(gv[x[i]][j] & gv[y[i]][j]);
	}
	tot /= 3;
	printf("%d\n",tot);

	return 0;
}