Cod sursa(job #1124182)

Utilizator catalincraciunCraciun Catalin catalincraciun Data 26 februarie 2014 11:42:56
Problema Triplete Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.56 kb
/// Craciun Catalin
///  Triplete
///   Infoarena
///    PreONI 2007, Runda 1
///     www.infoarena.ro/problema/triplete
///      Parcurgere bruta: Prima metoda de rezolvare e bruta si are complexitate exponentiala: O((n*(n+1)/2)*n)
///       A doua metoda de rezolvare foloseste matricea de adiacenta
#include <fstream>
#include <iostream>
#include <bitset>

#define NMax1 4100
#define NMax2 605
#define MMax 65540
#define DEBUG 1

using namespace std;

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

int n,m;
int X[MMax], Y[MMax];
bitset<NMax1> M[NMax1];
long triplete=0;

void afisare()
{
#ifdef DEBUG
    for (int i=1;i<=m;i++)
        cout<<X[i]<<' '<<Y[i]<<endl;
#endif // DEBUG
}

void parcurgereEficienta()
{
    f>>n>>m;
    for (int i=1;i<=m;i++)
    {
        f>>X[i]>>Y[i];
        M[X[i]][Y[i]]=M[Y[i]][X[i]]=1;
    }
    f.close();

    for (int i=1;i<=m;i++)
        triplete+=(M[X[i]]&M[Y[i]]).count();

    g<<triplete/3<<'\n';
    g.close();
}

void parcurgereBruta()
{
    bool A[NMax2][NMax2]; /// Matricea de adiacenta

    f>>n>>m;
    for (int i=1;i<=m;i++)
    {
        int x,y;
        f>>x>>y;
        A[x][y]=A[y][x]=true;
    }

    f.close();

    for (int i=1;i<=n;i++)
        for (int j=i+1;j<=n;j++)
            for (int k=j+1;k<=n;k++)
                if (A[i][j] && A[j][k] && A[k][i])
                    triplete++;

    g<<triplete<<'\n';
    g.close();
}

int main()
{
    if (n<=600)
        parcurgereBruta();
    else
        parcurgereEficienta();

    return 0;
}