Pagini recente » Cod sursa (job #1791630) | Cod sursa (job #9096) | Cod sursa (job #2683324) | Cod sursa (job #541079) | Cod sursa (job #3248093)
#include <fstream>
using namespace std;
const int N = 4096;
const int NB = 32;///vom folosi unsigned int, care e retinut pe 32 de biti
unsigned int a[N][N/NB];
int x[N], y[N];
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++)
{
nrt += nr_biti_1(a[x[i]][j] & a[y[i]][j]);
}
}
out << nrt / 3 << "\n";///fiecare triplet a fost numarat pentru fiecare pereche
///deci de 3 ori
in.close();
out.close();
return 0;
}