Artifact Content
Not logged in

Artifact bd2409ddf241ebbe72c10733f537662194b5ece9


#include <iostream>
#include <sstream>
#include <iomanip>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>
#include <iterator>
#include <functional>
#include <complex>
#include <queue>
#include <stack>
#include <cmath>
#include <cassert>
#include <cstring>
using namespace std;
typedef long long LL;
typedef complex<double> CMP;

class RoadsOfKingdom { public:
	vector< vector<double> > P;

	double getProbability(vector <string> roads) 
	{
		P     = read_input(roads);
		memo  = vector<double>(1<<P.size(), -1);
		memo0 = vector<double>(P.size()<<P.size(), -1);
		memo1 = vector<double>(P.size()<<P.size(), -1);
		return prob_tree( (1<<P.size())-1 );
	}

	vector< vector<double> > read_input(const vector<string>& R)
	{
		int N = R.size();
		vector< vector<double> > P(N, vector<double>(N));
		for(int i=0; i<N; ++i)
			for(int j=0; j<N; ++j)
				P[i][j] = (R[i][j] - '0') / 8.0;
		return P;
	}

	vector<double> memo;
	double prob_tree(int S)
	{
		if( memo[S] >= 0 )
			return memo[S];

		// the first and the second smallest IDs in S
		int v, w;
		for(v=0;   (1<<v)<=S; ++v) if( S & 1<<v ) break;
		for(w=v+1; (1<<w)<=S; ++w) if( S & 1<<w ) break;

		// if |S| < 2 then it always forms a tree
		if( (1<<w) > S )
			return memo[S] = 1.0;

		// Let's consider v as the "root node" of S, and try all possible "subtrees" T containing w.
		// The situation is (other nodes)=v-(T where w in T)
		double p = 0.0;
		for(int T=S; T; T=(T-1)&S)
			if( (T & 1<<w) && !(T & 1<<v) )
				p += prob_tree(T) * prob_tree(S&~T) * prob_separated(T, S&~T&~(1<<v)) * prob_one(v, T);
		return memo[S] = p;
	}

	double prob_separated(int S1, int S2)
	{
		double p = 1.0;
		for(int v=0; (1<<v)<=S1; ++v) if( S1 & 1<<v )
			p *= prob_zero(v, S2);
		return p;
	}

	vector<double> memo0;
	double prob_zero(int v, int S) // 0 connection between v and S
	{
		const int key = v<<P.size() | S;
		if( memo0[key] >= 0 ) return memo0[key];

		double p = 1.0;
		for(int u=0; (1<<u)<=S; ++u) if( S & 1<<u )
			p *= 1.0 - P[v][u];
		return memo0[key] = p;
	}

	vector<double> memo1;
	double prob_one(int v, int S) // exactly 1 connection between v and S
	{
		const int key = v<<P.size() | S;
		if( memo1[key] >= 0 ) return memo1[key];

		double p = 0.0;
		for(int c=0; (1<<c)<=S; ++c) if( S & 1<<c )
		{
			double q = 1.0;
			for(int u=0; (1<<u)<=S; ++u) if( S & 1<<u )
				q *= u==c ? P[v][u] : 1-P[v][u];
			p += q;
		}
		return memo1[key] = p;
	}
};

// BEGIN CUT HERE
#include <ctime>
double start_time; string timer()
 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
 { os << "{ ";
   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
void verify_case(const double& Expected, const double& Received) {
 bool ok = (abs(Expected - Received) < 1e-9);
 if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
#define END	 verify_case(_, RoadsOfKingdom().getProbability(roads));}
int main(){

CASE(0)
	string roads_[] = {"04",
 "40"};
	  vector <string> roads(roads_, roads_+sizeof(roads_)/sizeof(*roads_)); 
	double _ = 0.5; 
END
CASE(1)
	string roads_[] = {"08",
 "80"};
	  vector <string> roads(roads_, roads_+sizeof(roads_)/sizeof(*roads_)); 
	double _ = 1.0; 
END
CASE(2)
	string roads_[] = {"00",
 "00"};
	  vector <string> roads(roads_, roads_+sizeof(roads_)/sizeof(*roads_)); 
	double _ = 0.0; 
END
CASE(3)
	string roads_[] = {"088",
 "808",
 "880"};
	  vector <string> roads(roads_, roads_+sizeof(roads_)/sizeof(*roads_)); 
	double _ = 0.0; 
END
CASE(4)
	string roads_[] = {"044",
 "404",
 "440"};
	  vector <string> roads(roads_, roads_+sizeof(roads_)/sizeof(*roads_)); 
	double _ = 0.375; 
END
CASE(5)
	string roads_[] = {"0701",
 "7071",
 "0708",
 "1180"};
	  vector <string> roads(roads_, roads_+sizeof(roads_)/sizeof(*roads_)); 
	double _ = 0.622314453125; 
END
CASE(6)
	string roads_[] = {"0622100102300020", "6070000107208008", "2700207010110410", "2000188001010820", "1021032008000021", "0008300013001000", "0078200200000201", "1100002007000011", "0010010000600000", "2701830700518172", "3210000065000200", "0011000001002081", "0800010008020100", "0048002001201000", "2012200107080000", "0800101102010000"};
	  vector <string> roads(roads_, roads_+sizeof(roads_)/sizeof(*roads_)); 
	double _ = 5.519032471358341E-5; 
END
/*
CASE(7)
	string roads_[] = ;
	  vector <string> roads(roads_, roads_+sizeof(roads_)/sizeof(*roads_)); 
	double _ = ; 
END
*/
}
// END CUT HERE