Cod sursa(job #961048)

Utilizator primulDarie Sergiu primul Data 11 iunie 2013 16:34:59
Problema Triplete Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.98 kb
#include <cstdio>
#include <algorithm>
#include <vector>
#define pii pair<int,int>
#define x first
#define y second
#define mp make_pair
 
using namespace std;
 
const int NMAX = 100002;
pii E[NMAX];
int N, M;
int ans;
int high[NMAX];
 
void readData() {
    scanf("%d %d",&N,&M);
    for(int i = 0;i < M;i++) {
        scanf("%d %d",&E[i].x,&E[i].y);
        if(E[i].x > E[i].y) {
            swap(E[i].x,E[i].y);
        }
    }
}
 
int main()
{
    freopen("triplete.in","r",stdin);
    freopen("triplete.out","w",stdout);
    readData();
    sort(E,E + M);
    for(int i = 0;i < M;i++) {
        high[E[i].x] = max(high[E[i].x],i + 1);
    }
    for(int i = 0;i < M;i++) {
        if(high[E[i].y] > 0) {
            for(int j = i + 1;j < high[E[i].x];j++) {
                if(binary_search(E + i,E + high[E[i].y],mp(E[i].y,E[j].y))) {
                    ans++;
                }
            }
        }
    }
    printf("%d\n",ans);
    return 0;
}