Cod sursa(job #1484344)

Utilizator dnprxDan Pracsiu dnprx Data 10 septembrie 2015 21:16:35
Problema Triplete Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.04 kb
#include <bits/stdc++.h>

using namespace std;

unsigned a[4100][130];
int n, m, X[4100], Y[4100], Lim;

inline void SetBit(int k, int x)
{
    int q, r;
    q = x / 32;
    r = x % 32;
    a[k][q] |= (1 << (31 - r));
}

int NrBitiDe1(unsigned k)
{
    int nr = 0;
    while (k > 0)
    {
        nr++;
        k = k & (k - 1);
    }
    return nr;
}

void Citire()
{
    int i, p, q;
    ifstream fin("triplete.in");
    fin >> n >> m;
    Lim = n / 32 + 2;
    for (i = 1; i <= m; i++)
    {
        fin >> p >> q;
        if (p > q) swap(p, q);
        SetBit(p, q);
        X[i] = p;
        Y[i] = q;
    }
    fin.close();
}

void Rezolva()
{
    int i, j, x, y;
    long long cnt;
    cnt = 0;
    for (i = 1; i <= m; i++)
    {
        x = X[i];
        y = Y[i];
        for (j = 0; j < Lim; j++)
            cnt += NrBitiDe1(a[x][j] & a[y][j]);
    }
    ofstream fout("triplete.out");
    fout << cnt << "\n";
    fout.close();
}

int main()
{
    Citire();
    Rezolva();
    return 0;
}