Cod sursa(job #2443000)

Utilizator robert.barbu27robert barbu robert.barbu27 Data 26 iulie 2019 10:27:36
Problema Triplete Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.17 kb
#include <iostream>
#include <cmath>
#include <fstream>
#include <cstring>
#include <algorithm>

using namespace std;
ifstream f("triplete.in");
ofstream g("triplete.out");
struct elem{int un,doi;};elem v[132000];
int n,a,b,poz[4100],poz2[4100],nr=0,m;
bool compar(elem a1,elem a2){if(a1.un!=a2.un)return a1.un<a2.un;return a1.doi<a2.doi;}
int main()
{f>>m>>n;
int cnt=0;
for(int i=1;i<=n;i++)
{
    f>>a>>b;
    v[++cnt].un=a; v[cnt].doi=b;
    v[++cnt].un=b; v[cnt].doi=a;
}
sort(v+1,v+cnt+1,compar);
for(int i=1;i<=cnt;i++)
{if(poz[v[i].un]==0) poz[v[i].un]=i;
poz2[v[i].un]=i;
}
for(int i=1;i<=cnt;i++)
{
    while(v[i].un>v[i].doi) i++;
    if(i<=cnt)
    {
       int j=i+1;
        while(v[i].un==v[j].un)
        {
            int st=poz[v[i].doi];
            int dr=poz2[v[i].doi];
            int mij;
            bool ok=0;
            while(st<=dr)
            {
                mij=(st+dr)/2;
                if(v[mij].doi<v[j].doi) st=mij+1;

                  else  if(v[mij].doi>v[j].doi) dr=mij-1;
                    else {ok=1;break;}

            }
            if(ok==1) nr++;
            j++;
        }

    }
}
g<<nr;
}