Artifact 0ed1faf3d467caed87e24d035ad90cd5b066efd9
#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>
using namespace std;
typedef long long LL;
typedef long double LD;
typedef complex<double> CMP;
class TreeUnion { public:
double expectedCycles(vector <string> tree1, vector <string> tree2, int K)
{
vector<int> t1, t2;
{
stringstream sin(accumulate(tree1.begin(), tree1.end(), string()));
for(int v; sin>>v; ) t1.push_back(v);
}
{
stringstream sin(accumulate(tree2.begin(), tree2.end(), string()));
for(int v; sin>>v; ) t2.push_back(v);
}
int N = t1.size() + 1;
vector<vector<int> > d1 = make_d(t1, N);
vector<vector<int> > d2 = make_d(t2, N);
map<int, int> len_to_cnt_2;
for(int u=0; u<N; ++u)
for(int v=u+1; v<N; ++v)
len_to_cnt_2[d2[u][v]] += 2;
int total = N * (N-1);
double e = 0.0;
for(int u=0; u<N; ++u)
for(int v=u+1; v<N; ++v)
{
e += (double)len_to_cnt_2[K - 2 - d1[u][v]] / total;
}
return e;
}
vector<vector<int> > make_d(const vector<int>& x, int N)
{
vector<vector<int> > d(N, vector<int>(N, 0x3fffffff));
for(int i=0; i<N; ++i) d[i][i] = 0;
for(int i=0; i<x.size(); ++i) {
d[i+1][x[i]] = 1;
d[x[i]][i+1] = 1;
}
for(int k=0; k<N; ++k)
for(int i=0; i<N; ++i)
for(int j=0; j<N; ++j)
d[i][j] = min(d[i][j], d[i][k]+d[k][j]);
return d;
}
};
// 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(_, TreeUnion().expectedCycles(tree1, tree2, K));}
int main(){
CASE(0)
string tree1_[] = {"0"};
vector <string> tree1(tree1_, tree1_+sizeof(tree1_)/sizeof(*tree1_));
string tree2_[] = {"0"};
vector <string> tree2(tree2_, tree2_+sizeof(tree2_)/sizeof(*tree2_));
int K = 4;
double _ = 1.0;
END
CASE(1)
string tree1_[] = {"0 1"};
vector <string> tree1(tree1_, tree1_+sizeof(tree1_)/sizeof(*tree1_));
string tree2_[] = {"0 1"};
vector <string> tree2(tree2_, tree2_+sizeof(tree2_)/sizeof(*tree2_));
int K = 4;
double _ = 1.3333333333333333;
END
CASE(2)
string tree1_[] = {"0 1"};
vector <string> tree1(tree1_, tree1_+sizeof(tree1_)/sizeof(*tree1_));
string tree2_[] = {"0 1"};
vector <string> tree2(tree2_, tree2_+sizeof(tree2_)/sizeof(*tree2_));
int K = 6;
double _ = 0.3333333333333333;
END
CASE(3)
string tree1_[] = {"0 ", "1 1 1"};
vector <string> tree1(tree1_, tree1_+sizeof(tree1_)/sizeof(*tree1_));
string tree2_[] = {"0 1 0 ", "1"};
vector <string> tree2(tree2_, tree2_+sizeof(tree2_)/sizeof(*tree2_));
int K = 5;
double _ = 4.0;
END
CASE(4)
string tree1_[] = {"0 1 2 0 1 2 0 1 2 5 6 1", "0 11", " 4"};
vector <string> tree1(tree1_, tree1_+sizeof(tree1_)/sizeof(*tree1_));
string tree2_[] = {"0 1 1 0 2 3 4 3 4 6 6", " 10 12 12"};
vector <string> tree2(tree2_, tree2_+sizeof(tree2_)/sizeof(*tree2_));
int K = 7;
double _ = 13.314285714285713;
END
/*
CASE(5)
string tree1_[] = ;
vector <string> tree1(tree1_, tree1_+sizeof(tree1_)/sizeof(*tree1_));
string tree2_[] = ;
vector <string> tree2(tree2_, tree2_+sizeof(tree2_)/sizeof(*tree2_));
int K = ;
double _ = ;
END
CASE(6)
string tree1_[] = ;
vector <string> tree1(tree1_, tree1_+sizeof(tree1_)/sizeof(*tree1_));
string tree2_[] = ;
vector <string> tree2(tree2_, tree2_+sizeof(tree2_)/sizeof(*tree2_));
int K = ;
double _ = ;
END
*/
}
// END CUT HERE