Cod sursa(job #1750678)

Utilizator lflorin29Florin Laiu lflorin29 Data 30 august 2016 18:58:02
Problema Triplete Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.1 kb
#include <bits/stdc++.h>

using namespace std;
const int MAXN = 4097;

uint64_t cun[MAXN + 1][MAXN / 64 + 1];
vector <int> lista[MAXN +1];

int poz(int x) { return x&63;}
int unde(int x){return x>>6;}

void baga (int x, int y) {
	cun[x][unde(y)]|=1<<poz(y);}

bool este (int x, int y)
{
	return cun[x][unde(y)]&(1<<poz(y));
}
template<class T>
int ANDcnt(T a, T b) {
	int nr = a & b;
	return __builtin_popcount(nr);
}

template<class T>
void Cit(T &x)
{
	x = 0;
	char c = getchar();
	while(!isdigit(c)) c = getchar();
	while(isdigit(c))
	{
		x = x * 10 + c - '0';
		c = getchar();
	}
}
int main() {
	freopen("triplete.in", "r", stdin);
	freopen("triplete.out", "w", stdout);

	int N, M;

	Cit(N); Cit(M);
	for (int i = 0, x, y; i < M; ++i)
	{
		Cit (x); Cit (y);
		-- x; -- y;
		baga(x, y), baga (y, x);
		lista[x].push_back(y);
		lista[y].push_back(x);
	}
	long long ans = 0;

	for (int i = 0; i < N ; ++i)
	{
		for(auto j : lista[i]) {
			for(int k = 0; k < N; k += 64)
				ans += ANDcnt(cun[i][unde(k)], cun[j][unde(k)]);
		}
	}

	cout << ans / 6 ;
	return 0;
}