Cod sursa(job #1298716)

Utilizator diana97Diana Ghinea diana97 Data 23 decembrie 2014 01:16:05
Problema Triplete Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.73 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

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

const int NMAX = 4096 + 1, MMAX = 65536 + 1;

int n, m;
pair <int, int> muchie[NMAX];
vector <int> graf[NMAX];

void citeste() {
    f >> n >> m;
    int a, b;
    for (int i = 1; i <= m; i++) {
        f >> a >> b;
        graf[a].push_back(b);
        graf[b].push_back(a);
        muchie[i] = make_pair(a, b);
    }
}

void rezolva() {
    int x, y;
    long long sol = 0;
    vector <int> :: iterator it1, it2, end1, end2;
    for (int i = 1; i <= m; i++) {
        x = muchie[i].first;
        y = muchie[i].second;
        end1 = graf[x].end();
        end2 = graf[y].end();
        it1 = graf[x].begin();
        it2 = graf[y].begin();
        while (it1 != end1 && it2 != end2) {
            if (it2 != end2)
                while (it1 != end1 && *it1 < *it2) it1++;
            if (it1 != end1)
                while (it2 != end2 && *it2 < *it1) it2++;
            if (it1 != end1 && it2 != end2)
                if (*it1 == *it2) {sol++; it1++; it2++;}
        }
        for(i=1;i<=m;i++){
        x=b[i][0];
        y=b[i][1];
        end1=a[x].end();
        it1=a[x].begin();
        end2=a[y].end();
        it2=a[y].begin();
        while(it1!=end1 && it2!=end2){
            if(it2!=end2)
                while(it1!=end1 && *it1 < *it2) it1++;
            if(it1!=end1)
                while(it2!=end2 && *it2 < *it1) it2++;
            if(it1!=end1 && it2!=end2)
                if(*it1==*it2) {nr++;it1++;it2++;}}}
    }

    sol /= 3;

    g << sol << '\n';
}

int main() {
    citeste();
    for (int i = 1; i <= n; i++) sort(graf[i].begin(), graf[i].end());
    rezolva();
    return 0;
}