Cod sursa(job #7002)

Utilizator mariusdrgdragus marius mariusdrg Data 21 ianuarie 2007 11:38:32
Problema Triplete Scor 0
Compilator cpp Status done
Runda preONI 2007, Runda 1, Clasa a 10-a Marime 2.33 kb
#include<stdio.h>
#include<vector>
#include<algorithm>


using namespace std;


const int maxn = 4200;

vector <int>vect[maxn];
int m2;
int m1;
int x1;
int x2;
int i;
int j;
int ver[maxn];
int x;
int y;
int ma[maxn];
int nr;
int ad[maxn];
int n;
int m;




int bs(int i,int j)
{
        int m=vect[i].size()-1;
        int x=0;
        int p;
        for(p=1;p<=m;p<<=1);
        p>>=1;
        for(;p;p>>=1)
        {
                int aux=vect[i][x+p];
                if (vect[i][x+p]<=j) x+=p;
        }
        int aux=vect[i][x];
        if (aux<=j)  x++;
        return x;
}






int main()
{
        freopen("triplete.in","r",stdin);
        freopen("triplete.out","w",stdout);
        scanf("%d %d",&n,&m);
        for(i=1;i<=m;i++)
        {
                scanf("%d %d",&x,&y);
                vect[x].push_back(y);
                vect[y].push_back(x);
        }
        for(i=1;i<=n;i++)
        {
                sort(vect[i].begin(),vect[i].end());
        }
        for(i=1;i<=n;i++)
                for(j=i+1;j<=n;j++)
                {
                        m2=vect[j].size()-1;
                        x1=bs(i,j);
                        x2=bs(j,j);
                        m1=vect[i].size()-1;
                        while(x1<m1&&x2<m2)
                        {
                                int aux=vect[i][x1];
                                if (vect[i][x1]==vect[j][x2])
                                {
                                        nr++;
                                        x1++;
                                        x2++;
                                }
                                if (vect[i][x1]>vect[j][x2])
                                {
                                        x2++;
                                }
                                if (vect[i][x2]<vect[j][x1])
                                {
                                        x1++;
                                }
                        }
                        if (x1<=m1&&x2<=m2)
                        {
                                int aux=vect[i][x1];
                                if (vect[i][x1]==vect[j][x2]) nr++;
                        }
                
                }

        printf("%d\n",nr);
        return 0;
}