Cod sursa(job #8311)

Utilizator goguGogu Marian gogu Data 24 ianuarie 2007 12:37:49
Problema Triplete Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.09 kb
#include <stdio.h>
#include <vector>
#define MaxN 4096
#define pow(x) (1<<(x))

using namespace std;

unsigned n, m, sum[MaxN];
unsigned a[MaxN][MaxN/32];
vector <unsigned> V[MaxN];
unsigned vec[16*MaxN], st[2*MaxN];

inline int IsSet(unsigned x, unsigned y)
{
       return (a[x][y/32] & pow(y&31));
}

void Set(unsigned x, unsigned y)
{
     a[x][y/32] |= pow(y&31);
}

int main()
{
    freopen("triplete.in", "r", stdin);
    freopen("triplete.out", "w", stdout);
    unsigned i,j,k;
    scanf("%d %d", &n, &m);
    for (k=0; k<m; k++){
        scanf("%d %d", &i, &j);
        i--; j--;
        if (i<j) V[i].push_back(j), Set(i,j); 
           else V[j].push_back(i), Set(j,i);
    }
    for (i=0; i<n; i++){
        st[i+1]=st[i]+V[i].size();
        for (j=0; j<V[i].size(); j++)
            vec[st[i]+j]=V[i][j];
    }
    int sol=0;
    for (i=0; i<n; i++)
        for (j=st[i]; j<st[i+1]; j++){
            int v=vec[j];
            for (k=st[v]; k<st[v+1]; k++)
                if (IsSet(i, vec[k])) sol++;
        }
    printf("%d\n", sol);
    return 0;
}