Cod sursa(job #21549)

Utilizator astronomyAirinei Adrian astronomy Data 23 februarie 2007 20:33:42
Problema Triplete Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 1.54 kb
#include <stdio.h>
#include <stdlib.h>

#define MAXN (1 << 12)
#define swap(a,b) ((a)^=(b), (b)^=(a), (a)^=(b))

typedef unsigned int int_;

const int F = (1<<16)-1;

int N, M;

int_ G[MAXN][MAXN>>5];

int *V[MAXN], deg[MAXN];
int res, cnt[1<<16];


void baga(int_ u, int_ v)
{
    G[u][v>>5] |= (1 << (v & 31));
}

int bits(int_ x)
{
    return cnt[x&F]+cnt[(x>>16)&F];
}

int count(int x, int y)
{
    int i, r = 0;
    for(i = 0; i <= (N>>5); i++)
        r += bits(G[x][i]&G[y][i]);
    return r;
}

void solve(void)
{
    int i, x, y, *p;

    for(i = 1; i < (1<<16); i++)
        cnt[i] = cnt[i>>1] + (i&1);
        
    for(x = 0; x < N; x++)
     for(p = V[x]; *p; p++)
        res += count(x, *p);
}

int edge[1<<17][2];

void read_data(void)
{
    int i, u, v;

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

    for(i = 1; i <= M; i++)
    {
        scanf("%d %d\n", &u, &v);
        if(u > v) swap(u, v);
        u--, v--;
        baga(u, v);
        deg[u]++;
        edge[i][0] = u, edge[i][1] = v;
    }

    for(i = 0; i < N; i++)
        V[i] = (int*) malloc(sizeof(int)*(deg[i]+2)), V[i][deg[i]] = 0,
        deg[i] = 0;

    for(i = 1; i <= M; i++)
    {
        u = edge[i][0], v = edge[i][1];
        V[u][deg[u]++] = v;
    }
}

void write_data(void)
{
    printf("%d\n", res);
}

int main(void)
{
    freopen("triplete.in", "rt", stdin);
    freopen("triplete.out", "wt", stdout);

    read_data();
    solve();
    write_data();

    return 0;
}