Pagini recente » Cod sursa (job #467924) | Cod sursa (job #978323) | Cod sursa (job #2761637) | Cod sursa (job #2426867) | Cod sursa (job #3248100)
#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;
}