Cod sursa(job #3248100)

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

using namespace std;

const int N = 4096;
const int NB = 32;///vom folosi unsigned int, care e retinut pe 32 de biti
const int M = 65536;

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

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]--;
        int poz = y[i] / NB;///pozitia din a care contine codificarea coloanei y[i]
        int bit = y[i] % NB;///bitul lui poz corespunzator coloanei y[i]
        a[x[i]][poz] |= (1 << bit);
        poz = x[i] / NB;///pozitia din a care contine codificarea coloanei x[i]
        bit = x[i] % NB;///bitul lui poz corespunzator coloanei x[i]
        a[y[i]][poz] |= (1 << bit);
    }
    ///numaram tripletele parcurgand perechile de prieteni
    int nrt = 0;
    for (int i = 0; i < m; i++)
    {
        ///numaram prietenii comuni pentru perechea (x[i], y[i])
        ///adica numarul bitilor 1 ai rez. op. & intre elem liniilor x[i] si y[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";///fiecare triplet a fost numarat pentru fiecare pereche
    ///deci de 3 ori
    in.close();
    out.close();
    return 0;
}