Cod sursa(job #2561615)

Utilizator SergiuS3003Sergiu Stancu Nicolae SergiuS3003 Data 28 februarie 2020 23:32:37
Problema Triplete Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.34 kb
#include <fstream>
#include <algorithm>
#include <iostream>
using namespace std;
ifstream f ( "triplete.in" );
ofstream g ( "triplete.out" );
bool a[4100][4100];
struct relatii
{
    int x, y;
};
relatii M[66000];
bool cmpx ( relatii a, relatii b )
{
    if ( a.x == b.x )
        return a.y < b.y;

    return a.x < b.x;
}
int m;
int cautbin ( int poz )
{
    int p = poz, u = m, rasp = 0;

    while ( p <= u )
    {
        int mij = ( p + u ) / 2;

        if ( M[mij].x == M[poz].x )
        {
            p = mij + 1;
            rasp = mij;
        }
        else u = mij - 1;
    }

    return rasp;
}
int main()
{
    int x1, y1, N, nrt = 0;
    f >> N >> m;

    for ( int i = 1; i <= m; i++ )
    {
        f >> x1 >> y1;
        a[x1][y1] = a[y1][x1] = 1;
        M[i].x = min ( x1, y1 );
        M[i].y = max ( x1, y1 );
    }

    sort ( M + 1, M + m + 1, cmpx );
    M[0].x = 0;
    M[0].y = 0;

    for ( int i = 1; i < m; i++ )
        if ( M[i].x != M[i - 1].x && M[i].x == M[i + 1].x )
        {
            int poz1 = i;
            int poz2 = cautbin ( poz1 );

            for ( int j = poz1; j < poz2; j++ )
                for ( int k = j + 1; k <= poz2; k++ )
                    if ( a[M[k].y][M[j].y] == 1 )
                        nrt++;
        }

    g << nrt;
    return 0;
}