Cod sursa(job #71369)

Utilizator vlad_popaVlad Popa vlad_popa Data 10 iulie 2007 13:26:36
Problema Triplete Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.44 kb
using namespace std;

#include <cstdio>
#include <cassert>
#include <cstring>
#include <vector>
#include <algorithm>

#define FIN "triplete.in"
#define FOUT "triplete.out"
#define NMAX 4097
#define B 17
#define pb push_back

int NrBit1[1<<B];
int N, M, C[NMAX][(NMAX)/B+1];

void preproc ()
{
    int NrConf = (1<<B);

    for (int i = 0; i < NrConf; ++ i)
        for (int j = 0; j <= B; ++ j)
            if (i & (1 << j))
                ++ NrBit1[i];
}

void read ()
{
    scanf ("%d %d\n", &N, &M);

    int x, y;
    for (int i = 1; i <= M; ++ i)
    {
        scanf ("%d %d\n", &x, &y);
        -- x;
        -- y;
        C[x][y/B] += (1<<(y%B));
        C[y][x/B] += (1<<(x%B));
    }
}

void solve ()
{
    int sol = 0;
    fseek (stdin, 0, SEEK_SET);

    scanf ("%d %d\n", &N, &M);

    int x, y, szx, szy;
    for (int pas = 1; pas <= M; ++ pas)
    {
        scanf ("%d %d\n", &x, &y);
        -- x;
        -- y;

        int i;
        for (i = y + 1; (i % B); ++ i)
            if (C[x][i/B] & (1 << (i % B)))
                if (C[y][i/B] & (1 << (i % B)))
                    ++ sol;

        int sz = N / B;
        for (int j = i / B; j <= sz; ++ j)
            sol += NrBit1[C[x][j] & C[y][j]];
    }

    printf ("%d\n", sol);
}

int
 main ()
{
    freopen (FIN, "rt", stdin);
    freopen (FOUT, "wt", stdout);

    preproc ();
    read ();
    solve ();

    return 0;
}