Cod sursa(job #1631670)

Utilizator AlexandruValeanuAlexandru Valeanu AlexandruValeanu Data 5 martie 2016 17:59:19
Problema Triplete Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.87 kb
#include <bits/stdc++.h>

using namespace std;

constexpr int MAX_N = 4096;
constexpr int MAX_M = 65536;
constexpr int L = MAX_N / 32;

int G[MAX_N][L + 1];
pair<int,int> edge[MAX_M];
int N, M;

int main()
{
    ifstream in("triplete.in");
    ofstream out("triplete.out");

    in >> N >> M;

    for (int i = 0; i < M; ++i)
    {
        in >> edge[i].first >> edge[i].second;

        if (edge[i].first > edge[i].second)
            swap(edge[i].first, edge[i].second);

        edge[i].first--; edge[i].second--;

        G[ edge[i].first ][ edge[i].second >> 5 ] |= (1 << (edge[i].second & 31));
    }

    int solution = 0;

    for (int i = 0; i < M; ++i)
    {
        int &x = edge[i].first;
        int &y = edge[i].second;

        for (int j = 0; j <= L; ++j)
            solution += __builtin_popcount(G[x][j] & G[y][j]);
    }

    out << solution << "\n";

    return 0;
}