0
Your rating: None

CodeChef submission 773948 (C++ 4.3.2)

CodeChef submission 773948 (C++ 4.3.2) plaintext list. Status: WA, problem CIELWALK, contest . By hex539 (hex539), 2012-01-01 01:54:25.
  1. #include <cstdio>
  2. #include <vector>
  3. using namespace std;
  4. #define double long double
  5. #define fort(i) for (int i=T; i--;)
  6. #define fork(i,n) for (int i=n; i--;)
  7. int const T=72;
  8.  
  9. inline void to_infinity(double mat[T][T]){
  10.   static double tmp[T][T];
  11.   double want=0.0;
  12.   fort(i) fort(j) want+=mat[i][j];
  13.   fork(z,120){
  14.     double sum=0.0L;
  15.     fort(i) fort(j) tmp[i][j]=mat[i][j], mat[i][j]=0.0;
  16.     fort(i) fort(j) fort(k) mat[j][k]+=tmp[j][i]*tmp[i][k];
  17.     fort(i) fort(j) sum+=mat[i][j];
  18.     fort(i) fort(j) mat[i][j]*=want/sum;
  19.   }
  20. }
  21.  
  22. vector<int> edge[1000];
  23. bool flower[1000]={};
  24. int flow[1000];
  25. int flows=0;
  26.  
  27. int main(){
  28.   #ifdef twentyone
  29.   freopen("walk.in","r",stdin);
  30.   #endif
  31.  
  32.   int n,m,s; scanf("%d %d %d",&n,&m,&s);
  33.   int a,b;
  34.   for (int i=0; i<s; i++){
  35.     scanf("%d",&a); flower[--a]=1;
  36.     flow[i]=a; ++flows;
  37.   }
  38.   for (int i=0; i<m; i++){
  39.     scanf("%d %d",&a,&b);
  40.     edge[--a].push_back(--b);
  41.   }
  42.   edge[n-1].resize(1);
  43.   edge[n-1][0]=n-1;
  44.  
  45.   double prob[T][T]={};
  46.   fork(i,n) fork(j,n) prob[i][j]=(i==j and (flower[i] or i+1==n));
  47.   fork(i,n) if (not flower[i]) fork(j,edge[i].size()) prob[i][edge[i][j]]+=1.0/(double)edge[i].size();
  48.  
  49.   to_infinity(prob);
  50.   double pron[T][T]={};
  51.   fort(i) fort(j) pron[i][j]=prob[i][j], prob[i][j]=0.0L;
  52.   fort(i) fort(j) fork(k,edge[i].size()) prob[i][j]+=pron[edge[i][k]][j]/(double)edge[i].size();
  53.   fork(i,n) if (flower[i]) prob[i][i+n]+=prob[i][n-1], prob[i][n-1]=0.0L, prob[i+n][i+n]=1.0L;
  54.  
  55.   to_infinity(prob);
  56.  
  57.   for (int i=0; i<flows; i++)
  58.     printf("%.20Lf\n",prob[0][flow[i]+n]);
  59. }
  60.

Comments