Cod sursa(job #868961)

Utilizator Catah15Catalin Haidau Catah15 Data 31 ianuarie 2013 20:19:20
Problema Triplete Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.17 kb
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

#define cons 30
#define maxP 145
#define maxN 4100
#define PB push_back
#define MKP make_pair
#define f first
#define s second

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


inline int solve (int X)
{
    int ans = 0;

    for (int bit = 0; bit <= 30; ++ bit) if (X & 1 << bit) ++ ans;

    return ans;
}


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);

    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 % 30);
        List[y][x / cons] += 1 << (x % 30);
    }

    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 += solve (List[x][i] & List[y][i]);
    }

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

    return 0;
}