Cod sursa(job #16387)

Utilizator fireatmyselfBogdan-Alexandru Stoica fireatmyself Data 12 februarie 2007 22:11:57
Problema Triplete Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 1.14 kb
#include <stdio.h>
#define AMAX 4100
#define NMAX 140
#define MMAX 66000
#define B 30

int A[AMAX][NMAX], Cs[MMAX], Cd[MMAX], N, M;
int V[(1<<16)+2];

int main()
{
        int i, j, k, g, p, l, num = 0, cacat = 0;

        freopen("triplete.in", "r", stdin);
        scanf("%d %d", &N, &M);

        for (i = 0, l = (1<<16); i < l; i++, num = 0)
        {
            for (j = 0; j < 16; j++) num += ((i>>j)&1);
            V[i] = num;
        }

        for (k = 0; k < M; k++)
        {
                scanf("%d %d", &i, &j);
                Cs[k] = i; Cd[k] = j;
                p = j/B; g = j%B;
                A[i][p] += (1<<g);
                p = i/B; g = i%B;
                A[j][p] += (1<<g);
        }

        k = N/B;
        for (i = num = 0; i < M; i++)
                for (j = 0; j <= k; j++)
                {
                        p = A[ Cs[i] ][j]&A[ Cd[i] ][j];
                        l = p>>15; num += V[l];
                        l = p&((1<<15)-1); num += V[l];
                }

        freopen("triplete.out", "w", stdout);
        printf("%d\n", num/3);

        return 0;
        
}