Cod sursa(job #1450495)

Utilizator Bogdan15Bogdan Gherghina Bogdan15 Data 13 iunie 2015 15:20:20
Problema Triplete Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.28 kb
#include<fstream>
#include<algorithm>
#include<vector>
#define NMAX 4097
using namespace std;
ifstream f("triplete.in");
ofstream g("triplete.out");
vector<vector<int> >v(NMAX);
short N;
int M;
void citire(){
     f>>N;
     f>>M;
     int i;
     short x,y;
     for(i=1;i<=M;i++){
        f>>x;
        f>>y;
        if(x>y)
            swap(x,y);
        v[x].push_back(y);
     }
     f.close();
}
void sortare(){
     int i;
     for(i=1;i<=N;i++)
        sort(v[i].begin(),v[i].end());
}
bool cautare_binara(int a,int b){
     int mijloc,stanga=0,dreapta=v[a].size()-1;
     while(stanga<=dreapta){
        mijloc=(stanga+dreapta)/2;
        if(v[a][mijloc]==b)
            return 1;
        else{
            if(v[a][mijloc]<b)
                stanga=mijloc+1;
            else
                dreapta=mijloc-1;
        }
     }
     return 0;
}
long long rezolvare(){
     int i,j,k;
     long long nrt=0;
     for(i=1;i<=N;i++){
        for(j=0;j<v[i].size();j++){
            for(k=j+1;k<v[i].size();k++){
                if(cautare_binara(v[i][j],v[i][k]))
                    nrt++;
            }
        }
     }
     return nrt;
}
int main(){
     citire();
     sortare();
     g<<rezolvare();
     g.close();
     return 0;
}