Cod sursa(job #1750686)

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

using namespace std;
const int MAXN = 4097, MSK = (1<<16)-1;

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

int Biti[(1 << 16) + 1];

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

inline int ANDcnt(unsigned long long tt) {
	int res = 0;
	for (; tt ; tt >>= 16)
		res += Biti[tt & MSK];
	return res;
}

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

    Biti[0] = 0;
    for(int i = 1 ; i <= (1 << 16) ; ++i)
		Biti[i] = Biti[i >> 1] + (i & 1);

    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, pz = 0; k < N; k += 64, pz ++)
                ans += ANDcnt(cun[i][pz] & cun[j][pz]);
        }
    }

    cout << ans / 6 ;
    return 0;
}