Cod sursa(job #1977799)

Utilizator Coroian_DavidCoroian David Coroian_David Data 6 mai 2017 10:27:43
Problema Triplete Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.51 kb
/**
*   Problema se poate rezolva cu O(N^3) amortizat sau O(N^2 + M), dar nu e optim.
*
*   Vom marca vecinii lui i cu un bitset de mana, cate 32, luam fiecare doi vecini si adunam bitii comuni.
*
*   Time Complexity : O(M * N / bits), unde bits e 32
*
*   COROIAN DAVID, Satu Mare, ROMANIA
**/

#include <cstdio>

using namespace std;

FILE *f, *g;

long long v[4100][130];

int a[70009];
int b[70009];

int one[70009];

void add(int a, int b)
{
    v[a][b / 32] |= 1LL << (b % 32);
}

int n, m;

void readFile()
{
    f = fopen("triplete.in", "r");

    fscanf(f, "%d%d", &n, &m);

    int i;
    for(i = 1; i <= m; i ++)
    {
        fscanf(f, "%d%d", &a[i], &b[i]);

        add(a[i], b[i]);
        add(b[i], a[i]);
    }

    fclose(f);
}

void bits()
{
    int i, p2 = 1 << 16;
    for(i = 1; i <= p2; i ++)
        one[i] = one[i >> 1] + (i & 1);///bitii de 1 lui 10011001101 sunt bitii de unu lui 1001100110 + ultimul bit
}

const int p2 = (1 << 16) - 1;

int ones(long long x)
{
    ///    primii 16        ultimii 16
    return one[x >> 16] + one[x & p2];
}

int rez;

void solve()
{
    bits();

    n /= 32;

    int i, j;
    for(i = 1; i <= m; i ++)
    {
        for(j = 0; j <= n; j ++)
            rez += ones(v[a[i]][j] & v[b[i]][j]);
    }
}

void printFile()
{
    g = fopen("triplete.out", "w");

    fprintf(g, "%d\n", rez / 3);

    fclose(f);
}

int main()
{
    readFile();

    solve();

    printFile();

    return 0;
}