Cod sursa(job #7281)

Utilizator mariusdrgdragus marius mariusdrg Data 21 ianuarie 2007 13:18:33
Problema Triplete Scor 80
Compilator cpp Status done
Runda preONI 2007, Runda 1, Clasa a 10-a Marime 3.43 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 nr;
int ad[maxn];
int n;
int m;
int st[maxn];
int x11;


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++)
        {
                vector<int>:: iterator it;
                for(it=vect[i].begin(),j=0;it!=vect[i].end();++j, ++it)
                {
                        if (*it>i)
                        {
                                st[i] = j;
                                break;
                        }
                }
        }
        for(i=1;i<=n;i++)
        {
                x11=st[i];

                for(j=i+1;j<=n;j++)
                {
                        m2=vect[j].size()-1;
                    //    x1=bs(i,j);
                        m1=vect[i].size()-1;
                     
                        if (vect[i][x11]<=j)  x11++;
                        x1=x11;
                        if (x1>m1) continue;
                        if (vect[i][x1-1]!=j) continue;
                   
                 /*       int aux=vect[i][x1-1];
                        x2=bs(j,j);          */
                        x2=st[j];
                        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][x1]<vect[j][x2])
                                {
                                        x1++;
                                }
                        }
                        if (x1<=m1&&x2<=m2)
                        {
                                int aux=vect[j][x2];
                                while(x1<m1||x2<m2)
                                {

                                        if (vect[i][x1]==vect[j][x2]) nr++;
                                        if (x1<m1) x1++;
                                        if (x2<m2) x2++;
                                }
                                if (vect[i][x1]==vect[j][x2]) nr++;
                                       
                        }
                
                }

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