Cod sursa(job #325224)

Utilizator doru.nituNitu Doru Constantin doru.nitu Data 19 iunie 2009 16:09:16
Problema Triplete Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.29 kb
#include<stdio.h>
#include<algorithm>
using namespace std;

struct nod
{ int p[2001];
}a[4100];

int i,j,k,n,m,x,y,p,ok1,ok,rez,mij;

int cautbin(int x,int i)
{ int st=1,dr=a[i].p[0];
  bool ok=0;
  while(st<=dr&&!ok)
         { mij=(st+dr)/2;
           if(a[i].p[mij]==x) ok=1;
           else if(x>a[i].p[mij]) st=mij+1;
           else dr=mij-1;
         }
  if(ok) return 1;
  return 0;
}
             

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);
                        a[x].p[++a[x].p[0]]=y;
                      }
    for(i=1;i<=m;i++) if(a[i].p[0]) sort(a[i].p+1,a[i].p+a[i].p[0]+1);                  
    //for(i=1;i<=m;i++){
    // for(j=1;j<=a[i].p[0];j++) printf("%d ",a[i].p[j]);
    //                   printf("\n");
      //               }                     
                        
                      
                      
     for(i=1;i<=n;i++)   if(a[i].p[0])  for(j=1;j<=a[i].p[0];j++)
                                        if(a[a[i].p[j]].p[0])for(k=1;k<=a[a[i].p[j]].p[0];k++) { ok=cautbin(a[a[i].p[j]].p[k],i);
                                                                                if(!ok) { 
                                                                                         // ok1=cautbin(i,a[a[i].p[j]].p[k]);
                                                                                          //if(ok1){ rez++;
                                                                                                  // printf("%d %d %d\n",a[i].p[j],a[a[a[i].p[j]].p[k]].p[mij],i);
                                                                                             //    } 
                                                                                        }                                        
                                                                                else rez++;//,printf("%d %d %d\n",i,a[i].p[j],a[a[i].p[j]].p[k]);
                                                                              }
    printf("%d\n",rez);
    fclose(stdin);
    fclose(stdout);
    return 0;
}