Cod sursa(job #369674)

Utilizator DraStiKDragos Oprica DraStiK Data 29 noiembrie 2009 10:01:09
Problema Triplete Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.93 kb
#include <algorithm>
#include <vector>
using namespace std;

#define pb push_back
#define DIM 4100
#define LOG 16

int lst[DIM][DIM/LOG+1];
int nrb[(1<<LOG)+1];
int n,m,nrt;

void read ()
{
    int i,x,y;

    scanf ("%d%d",&n,&m);
    for (i=1; i<=m; ++i)
    {
        scanf ("%d%d",&x,&y);
        lst[x][y/LOG]|=(1<<(y%LOG));
        lst[y][x/LOG]|=(1<<(x%LOG));
    }
}

void init ()
{
    int i;

    for (i=1; i<=(1<<LOG); ++i)
        nrb[i]=nrb[i>>1]+(i&1);
}

void solve ()
{
    freopen ("triplete.in","r",stdin);
    int i,j,x,y;

    scanf ("%d%d",&n,&m);
    for (i=1; i<=m; ++i)
    {
        scanf ("%d%d",&x,&y);
        for (j=0; j<=DIM/LOG; ++j)
            nrt+=nrb[(lst[x][j]&lst[y][j])];
    }
    printf ("%d",nrt/3);
}

int main ()
{
    freopen ("triplete.in","r",stdin);
    freopen ("triplete.out","w",stdout);

    read ();
    init ();
    solve ();

    return 0;
}