Pagini recente » Cod sursa (job #105590) | Cod sursa (job #201881) | Cod sursa (job #1566279) | Cod sursa (job #1248976) | Cod sursa (job #1124507)
/// 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;
}