Pagini recente » Cod sursa (job #1158246) | Cod sursa (job #2466939) | Cod sursa (job #667196) | Cod sursa (job #1889137) | Cod sursa (job #355362)
Cod sursa(job #355362)
#include <fstream>
#include <vector>
using namespace std;
typedef unsigned int uint;
const int NMAX=4096;
const int BASE=32;
const int MASK=(1<<(BASE>>1)) - 1;
uint B[NMAX][(NMAX/BASE)+1];
int N,M,HalfBits[1<<(BASE>>1)];
vector<int> G[NMAX];
void add(int i,int j)
{
int c,r;
c=j/BASE;
r=j%BASE;
B[i][c]|=(1<<r);
G[i].push_back(j);
}
int NrBiti(uint n)
{
return HalfBits[n&MASK]+HalfBits[n>>(BASE>>1)];
}
int main()
{
int i,j;
ifstream fin("triplete.in");
ofstream fout("triplete.out");
fin>>N>>M;
while (M--)
{
fin>>i>>j;
i--;j--;
add(i,j);
add(j,i);
}
for (i=1;i<(1<<(BASE>>1));++i)
HalfBits[i]=HalfBits[i>>1]+(i&1);
long long sol=0;
vector<int>::iterator it;
for (i=0;i<N;++i)
for (it=G[i].begin();it!=G[i].end();++it)
for (j=0;j<=(N/BASE);++j)
sol+=NrBiti(B[i][j]&B[*it][j]);
fout<<sol/6;
return 0;
}