Cod sursa(job #2416603)

Utilizator carburatorMitica Carburator carburator Data 27 aprilie 2019 19:46:56
Problema Triplete Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.03 kb
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("triplete.in");
ofstream fout("triplete.out");
struct elem{int un,doi;}; elem v[131075];
bool compar(elem a1, elem a2){if(a1.un!=a2.un)return a1.un<a2.un; return a1.doi<a2.doi;}
long long i,N,M,poz[4100],poz2[4100],a,b,y,j,st,dr,m,ok,nr;
int main()
{
    fin>>N>>M;
    for(i=1;i<=M;i++){ fin>>a>>b;
     v[++y].un=a; v[y].doi=b;
     v[++y].un=b; v[y].doi=a;
    }
    sort(v+1,v+y+1,compar);

    for(i=1;i<=y;i++){
        if(!poz[v[i].un])poz[v[i].un]=i;
        poz2[v[i].un]=i;
    }

    for(i=1;i<=y;i++){
       while(v[i].un>v[i].doi)i++;
       if(i<=y){ j=i+1;
         while(v[i].un==v[j].un){
            st=poz[v[i].doi]; dr=poz2[v[i].doi]; ok=0;
            while(st<=dr){ m=(st+dr)/2;
                if(v[m].doi<v[j].doi)st=m+1;
               else if(v[m].doi>v[j].doi)dr=m-1;
                else {ok=1; break;}
            }
            if(ok)nr++;
            j++;
         }
       }
    }
    fout<<nr;

    return 0;
}