Cod sursa(job #39821)

Utilizator DastasIonescu Vlad Dastas Data 26 martie 2007 23:23:34
Problema Triplete Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.88 kb
#include <iostream>
#include <fstream>

using namespace std;

ifstream in("triplete.in");
ofstream out("triplete.out");

int n, m;

//void read()
//{
//    in >> N >> M;
//    int x, y;
//    for ( int i = 0; i < M; ++i )
//    {
//        in >> x >> y;
//        a[x-1][y-1] = a[y-1][x-1] = 1;
//    }
//}
//
//void printmat()
//{
//    for ( int i = 0; i < N; ++i )
//    {
//        for ( int j = 0; j < N; ++j )
//            cout << a[i][j] << " ";
//        cout << endl;
//    }
//}
//
//void rez()
//{
//    int cnt = 0;
//    for ( int i = 0; i < N; ++i )
//        for ( int j = i; j < N; ++j )
//            for ( int k = j; k < N; ++k )
//            {
//                if ( a[i][j] == 1 && a[i][j] == a[i][k] && a[j][k] == a[i][k] )
//                    ++cnt;
//            }
//
//    out << cnt << endl;
//}
//
void rezbiti()
{
    //unsigned int a[409][12];
    in >> n >> m;
    unsigned int **a = new unsigned int*[4096];
    memset(a,0,4096);
    for ( int i = 0; i < 4096; ++i )
        a[i] = new unsigned int[128], memset(a[i], 0, 128);



    struct perechi
    {
        unsigned int a, b;
    };

    unsigned char L[256];

    perechi *b = new perechi[65537];
    for ( int i = 0; i < m; ++i )
    {
        in >> b[i].a >> b[i].b;
        b[i].a -= 1;
        b[i].b -= 1;
        a[b[i].a][b[i].b/32] |= (1<<(b[i].b%32));
        a[b[i].b][b[i].a/32] |= (1<<(b[i].a%32));
    }

    int cnt = 0;
    int s = (n+31)/32;
    for ( int i = 0; i < m; ++i )
    {
        for ( int j = 0; j < s; ++j )
        {
            int t = a[b[i].a][j] & a[b[i].b][j];
            for ( int biti = 0; biti < 32; ++biti )
            {
                cnt += (t & (1<<biti)) != 0;
            }
        }
    }

    out << cnt/3 << endl;
}

int main()
{
    //read();
    //printmat();
    rezbiti();

	return 0;
}