Pagini recente » Cod sursa (job #140806) | Cod sursa (job #2668924) | Cod sursa (job #1386312) | Cod sursa (job #1466908) | Cod sursa (job #1977798)
/**
* Problema se poate rezolva cu O(N^3) amortizat sau O(N^2 + M), dar nu e optim.
*
* Vom marca vecinii lui i cu un bitset de mana, cate 32, luam fiecare doi vecini si adunam bitii comuni.
*
* Time Complexity : O(M * N / bits), unde bits e 32
*
* COROIAN DAVID, Satu Mare, ROMANIA
**/
#include <cstdio>
using namespace std;
FILE *f, *g;
unsigned int v[4100][130];
int a[70009];
int b[70009];
int one[70009];
void add(int a, int b)
{
v[a][b / 32] |= 1 << (b % 32);
}
int n, m;
void readFile()
{
f = fopen("triplete.in", "r");
fscanf(f, "%d%d", &n, &m);
int i;
for(i = 1; i <= m; i ++)
{
fscanf(f, "%d%d", &a[i], &b[i]);
add(a[i], b[i]);
add(b[i], a[i]);
}
fclose(f);
}
void bits()
{
int i, p2 = 1 << 16;
for(i = 1; i <= p2; i ++)
one[i] = one[i >> 1] + (i & 1);///bitii de 1 lui 10011001101 sunt bitii de unu lui 1001100110 + ultimul bit
}
const int p2 = (1 << 16) - 1;
int ones(int x)
{
/// primii 16 ultimii 16
return one[x >> 16] + one[x & p2];
}
int rez;
void solve()
{
bits();
n /= 32;
int i, j;
for(i = 1; i <= m; i ++)
{
for(j = 0; j <= n; j ++)
rez += ones(v[a[i]][j] & v[b[i]][j]);
}
}
void printFile()
{
g = fopen("triplete.out", "w");
fprintf(g, "%d\n", rez / 3);
fclose(f);
}
int main()
{
readFile();
solve();
printFile();
return 0;
}