Cod sursa(job #1145300)

Utilizator marta_diannaFII Filimon Marta Diana marta_dianna Data 18 martie 2014 08:54:06
Problema Triplete Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.08 kb
#include<fstream>
#define NMAX 4100
#define MMAX 300
#define NRMUCHII 70000

using namespace std;

unsigned int n, m, a[NMAX][MMAX];

struct muchie
{
    int nod1, nod2;
}x[NRMUCHII];

ifstream f("triplete.in");
ofstream g("triplete.out");

void Adauga(int nod1, int nod2)
{
    unsigned int x, y;
    x=nod2/16; y=nod2%16;
    a[nod1][x]=a[nod1][x]|(1<<y);
}

void Citeste()
{
    int i, nod1, nod2, aux;

    f>>n>>m;

    for (i=1; i<=m; ++i)
    {
        f>>nod1>>nod2;
        x[i].nod1=nod1; x[i].nod2=nod2;
        Adauga(nod1, nod2);
        Adauga(nod2, nod1);
    }
}

inline int count(unsigned int x)
{
    int sol=0;
    if (x)
        do{ ++sol; }while (x&=x-1);
    return sol;
}

void Solve()
{
    int j, i, lim=(n/16)+1;
    long long nr=0;
    muchie aux;

    for (i=1; i<=m; ++i)
    {
        aux=x[i];
        for (j=0; j<=lim; ++j)
            nr+=count(a[aux.nod1][j]&a[aux.nod2][j]);
    }

    g<<nr/3<<"\n";
}

int main()
{
    Citeste();

    Solve();

    f.close();
    g.close();
    return 0;
}