Cod sursa(job #1124507)

Utilizator catalincraciunCraciun Catalin catalincraciun Data 26 februarie 2014 12:33:52
Problema Triplete Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.77 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 sizeNr 1500000
#define MMax 65540

using namespace std;

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

int n,m;
int X[MMax], Y[MMax];
bitset<NMax1> M[NMax1];
long long triplete=0;
char nr[sizeNr], *pointerToNr=nr;

inline int atoi()
{
    int x=0;

    for (;!(*pointerToNr>='0' && *pointerToNr<='9'); ++pointerToNr);
    for (;*pointerToNr>='0' && *pointerToNr<='9'; ++pointerToNr)
        x=x*10+(*pointerToNr-'0');

    return x;
}

void parcurgereEficienta()
{
    m=atoi();
    for (int i=1;i<=m;i++)
    {
        X[i]=atoi();
        Y[i]=atoi();
        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>>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()
{
    f.read(nr, sizeNr); n=atoi();
    if (n<=500)
        parcurgereBruta();
    else
        parcurgereEficienta();

    return 0;
}