Cod sursa(job #549129)

Utilizator AdamSVlad Adam AdamS Data 8 martie 2011 10:17:09
Problema Triplete Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.53 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;
}