Cod sursa(job #869319)

Utilizator Catah15Catalin Haidau Catah15 Data 1 februarie 2013 13:41:06
Problema Triplete Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.2 kb
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

#define cons 16
#define maxP 2 * 145
#define maxN 4100
#define maxX 65600
#define PB push_back
#define MKP make_pair
#define f first
#define s second

vector <pair <int, int> > edges;
vector <int> List[maxN];
int bits[maxX];


void prec ()
{
    for(int i = 1; i < maxX - 3; ++ i)
       bits[i] = bits[i >> 1] + (i & 1);
}


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

    int N, M;
    scanf ("%d %d", &N, &M);

    for (int i = 1; i <= N; ++ i)
        for (int j = 1; j <= maxP - 3; ++ j) List[i].PB (0);

    prec ();

    for (int i = 1; i <= M; ++ i)
    {
        int x, y;
        scanf ("%d %d", &x, &y);

        edges.PB ( MKP (x, y) );

        List[x][y / cons] += 1 << (y % cons);
        List[y][x / cons] += 1 << (x % cons);
    }

    int sol = 0;

    for (int i = 0; i < M; ++ i)
    {
        int x = edges[i].f, y = edges[i].s;

        for (int i = 0; i <= maxP - 3; ++ i) sol += bits [List[x][i] & List[y][i]];
    }

    printf ("%d", sol / 3);

    return 0;
}