Cod sursa(job #3247963)

Utilizator rapidu36Victor Manz rapidu36 Data 10 octombrie 2024 09:10:56
Problema Triplete Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.22 kb
#include <fstream>

using namespace std;

const int N = 4096;
const int M = 65536;
const int NB = 32;

int x[M], y[M];
unsigned int a[N][N/NB+1];

int nr_biti_1(int n)
{
    int nr = 0;
    while (n != 0)
    {
        nr++;
        n &= (n - 1);
    }
    return nr;
}

int main()
{
    ifstream in("triplete.in");
    ofstream out("triplete.out");
    int n, m;
    in >> n >> m;
    for (int i = 0; i < m; i++)
    {
        in >> x[i] >> y[i];
        x[i]--;
        y[i]--;
    }
    for (int i = 0; i < m; i++)
    {
        ///pentru prietenia x[i] cu y[i]
        int bit = y[i] % NB;///sau y[i] & (NB-1)
        a[x[i]][y[i]/NB] |= (1 << bit);///setez bitul y[i]%NB al lui a[x[i]][y[i]/NB] la 1
        bit = x[i] % NB;
        a[y[i]][x[i]/NB] |= (1 << bit);///setez bitul x[i]%NB al lui a[y[i]][x[i]/NB] la 1
    }
    int nrt = 0;///numaram tripletele facand & pe biti pentru fiecare pereche (x[i],y[i])
    for (int i = 0; i < m; i++)
    {
        for (int j = 0; j <= n / NB; j++)
        {
            int intersectie = a[x[i]][j] & a[y[i]][j];
            nrt += nr_biti_1(intersectie);
        }
    }
    out << nrt / 3 << "\n";
    in.close();
    out.close();
    return 0;
}