Cod sursa(job #8309)

Utilizator goguGogu Marian gogu Data 24 ianuarie 2007 12:32:03
Problema Triplete Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.03 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> vec[MaxN];

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

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

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