Cod sursa(job #523707)

Utilizator cosmyoPaunel Cosmin cosmyo Data 18 ianuarie 2011 22:54:26
Problema Triplete Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.84 kb
#include <cstdio>
#include <vector>
#include <algorithm>
#define f first
#define s second
using namespace std;
const int N = 5000;
int n, m, NR , w[N * 2], p[1 << 17], a1, a2;
int a[150][N];
pair<int, int> v[67000];

int main() {
	freopen("triplete.in", "r", stdin);
	freopen("triplete.out", "w", stdout);
	int k, aux, i, x, y, r ,nr, j;
	scanf("%d %d", &n, &m);
	for(i = 1; i <= m; ++i) 
		scanf("%d %d", &x, &y),	v[i].f = x - 1, v[i].s = y - 1, a[(y - 1) / 30][x - 1] += 1 << ((y - 1) % 30 ), a[(x - 1) / 30][y - 1] += 1 <<((x - 1) % 30);
	for(i = 1; i < 1 << 17; ++i) {
		aux = i;
		while(aux){ 
			if(aux % 2) ++p[i];
			aux /= 2;
		}
	}
	
	for(i = 1; i <= m; ++i) {
		nr = 0;
		r = 0;
		for(j = 0; j <= n / 30; ++j){
			k = a[j][v[i].f] & a[j][v[i].s];
			a1 = k % 100000;
			a2 = k / 100000;
			NR += p[a1] + p[a2];
		}
	}
	printf("%d\n", NR/3);
	return 0;
}