Cod sursa(job #7124)
Utilizator | Data | 21 ianuarie 2007 12:38:43 | |
---|---|---|---|
Problema | Triplete | Scor | 0 |
Compilator | cpp | Status | done |
Runda | preONI 2007, Runda 1, Clasa a 10-a | Marime | 2.79 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);
int aux=vect[i][x1-1];
if (vect[i][x1-1]!=j) continue;
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];
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;
}