Cod sursa(job #51696)

Utilizator alextheroTandrau Alexandru alexthero Data 16 aprilie 2007 15:11:21
Problema Triplete Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.12 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],i,j,n,m,sus,next,tot;
int gv[nmax][140],p[baza + 5],crt,start,finish;

void puteri() {
	p[0] = 1;
	for(i = 1; i <= baza; i++) p[i] = p[i - 1] * 2;
}

int main() {
	freopen("triplete.in","r",stdin);
	freopen("triplete.out","w",stdout);

	puteri();

	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++) {
		int p1 = 0;
		for(j = 1; j <= sus / baza; j++) {
			crt = 0;
			start = (j - 1) * baza + 1;
			finish = j * baza;
			while(p1 < (int)e[i].size() && e[i][p1] <= finish) {
				crt += p[finish - e[i][p1]];
				p1++;
			}
			gv[i][++gv[i][0]] = crt;
		}
	}

	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;
}