Pagini recente » Istoria paginii preoni-2004/runda-2/clasament-11-12 | Cod sursa (job #498469) | Cod sursa (job #492646) | Cod sursa (job #1463713) | Cod sursa (job #7485)
Cod sursa(job #7485)
#include <stdio.h>
#define NMAX 4100
#define MMAX 66000
const int mod16 = (1 << 16) - 1;
int N, M;
int xx[MMAX];
int yy[MMAX];
int nrb[(1 << 16) + 100];
unsigned int leg[NMAX][(NMAX >> 5) + 3];
inline void put(int x, int y)
{
leg[x][y >> 5] |= 1 << (y & 31);
}
inline unsigned int ex(int x, int y)
{
return (leg[x][y >> 5] & (1 << (y & 31)));
}
inline int nrb1(unsigned int x)
{
return nrb[x & mod16] + nrb[(x >> 16)];
}
/*
int solve_brute()
{
int i, j, k, rez = 0;
for (i = 1; i <= N; i++)
for (j = i + 1; j <= N; j++)
for (k = j + 1; k <= N; k++)
if (ex(i, j) && ex(i, k) && ex(j, k)) rez++;
return rez;
}
unsigned int legtemp[NMAX][(NMAX >> 5) + 3];
#include <stdlib.h>
int gen(int N, int M)
{
freopen("triplete.in", "w", stdout);
printf("%d %d\n", N, M);
int x, y;
for (int i = 1; i <= M; )
{
x = rand() % N + 1; y = rand() % N + 1;
if (x == y) continue;
if (legtemp[x][y >> 5] & (1 << (y & 31))) continue;
legtemp[x][y >> 5] |= 1 << (y & 31);
legtemp[y][x >> 5] |= 1 << (x & 31);
printf("%d %d\n", x, y);
i++;
}
fclose(stdout);
return 0;
}
*/
int main()
{
// srand(13);
// gen(4000, 65000);
int i, x, y;
freopen("triplete.in", "r", stdin);
freopen("triplete.out", "w", stdout);
nrb[0] = 0;
for (i = 1; i <= (1 << 16); i++)
nrb[i] = nrb[i >> 1] + (i & 1);
scanf("%d %d", &N, &M);
for (i = 1; i <= M; i++) {
scanf("%d %d", &xx[i], &yy[i]);
put(xx[i], yy[i]);
put(yy[i], xx[i]);
}
int q, j;
long long rez = 0;
unsigned int aux;
for (i = 1; i <= M; i++) {
x = xx[i]; y = yy[i];
q = 0;
for (j = 0; j < (N >> 5) + 3; j++) {
aux = leg[x][j] & leg[y][j];
q += nrb1(aux);
}
rez += q;
}
printf("%lld\n", rez / 3);
// printf("%d\n", solve_brute());
fclose(stdin);
fclose(stdout);
return 0;
}