d82ca3d4de 2014-05-29 kinaba: #include <iostream> d82ca3d4de 2014-05-29 kinaba: #include <sstream> d82ca3d4de 2014-05-29 kinaba: #include <iomanip> d82ca3d4de 2014-05-29 kinaba: #include <vector> d82ca3d4de 2014-05-29 kinaba: #include <string> d82ca3d4de 2014-05-29 kinaba: #include <map> d82ca3d4de 2014-05-29 kinaba: #include <set> d82ca3d4de 2014-05-29 kinaba: #include <algorithm> d82ca3d4de 2014-05-29 kinaba: #include <numeric> d82ca3d4de 2014-05-29 kinaba: #include <iterator> d82ca3d4de 2014-05-29 kinaba: #include <functional> d82ca3d4de 2014-05-29 kinaba: #include <complex> d82ca3d4de 2014-05-29 kinaba: #include <queue> d82ca3d4de 2014-05-29 kinaba: #include <stack> d82ca3d4de 2014-05-29 kinaba: #include <cmath> d82ca3d4de 2014-05-29 kinaba: #include <cassert> d82ca3d4de 2014-05-29 kinaba: #include <tuple> d82ca3d4de 2014-05-29 kinaba: using namespace std; d82ca3d4de 2014-05-29 kinaba: typedef long long LL; d82ca3d4de 2014-05-29 kinaba: typedef complex<double> CMP; d82ca3d4de 2014-05-29 kinaba: d82ca3d4de 2014-05-29 kinaba: class TreesAnalysis { public: d82ca3d4de 2014-05-29 kinaba: typedef int EID; d82ca3d4de 2014-05-29 kinaba: int N; d82ca3d4de 2014-05-29 kinaba: long long treeSimilarity(vector <int> tree1, vector <int> tree2) d82ca3d4de 2014-05-29 kinaba: { d82ca3d4de 2014-05-29 kinaba: N = tree1.size() + 1; d82ca3d4de 2014-05-29 kinaba: vector<vector<pair<EID,int>>> T1(N); d82ca3d4de 2014-05-29 kinaba: vector<vector<int>> T2(N); d82ca3d4de 2014-05-29 kinaba: for(int v=0; v<N-1; ++v) { d82ca3d4de 2014-05-29 kinaba: int u = tree1[v]; d82ca3d4de 2014-05-29 kinaba: T1[v].emplace_back(v, u); d82ca3d4de 2014-05-29 kinaba: T1[u].emplace_back(v+N, v); d82ca3d4de 2014-05-29 kinaba: } d82ca3d4de 2014-05-29 kinaba: for(int v=0; v<N-1; ++v) { d82ca3d4de 2014-05-29 kinaba: int u = tree2[v]; d82ca3d4de 2014-05-29 kinaba: T2[v].push_back(u); d82ca3d4de 2014-05-29 kinaba: T2[u].push_back(v); d82ca3d4de 2014-05-29 kinaba: } d82ca3d4de 2014-05-29 kinaba: d82ca3d4de 2014-05-29 kinaba: LL total = 0; d82ca3d4de 2014-05-29 kinaba: for(int v2=0; v2<N-1; ++v2) { d82ca3d4de 2014-05-29 kinaba: int u2 = tree2[v2]; d82ca3d4de 2014-05-29 kinaba: d82ca3d4de 2014-05-29 kinaba: function<void(int,int)> rec; d82ca3d4de 2014-05-29 kinaba: vector<bool> sub_vu(N), sub_uv(N, true); d82ca3d4de 2014-05-29 kinaba: rec = [&](int a, int b) { d82ca3d4de 2014-05-29 kinaba: sub_vu[b] = true; d82ca3d4de 2014-05-29 kinaba: sub_uv[b] = false; d82ca3d4de 2014-05-29 kinaba: for(int c: T2[b]) if(c!=a) d82ca3d4de 2014-05-29 kinaba: rec(b,c); d82ca3d4de 2014-05-29 kinaba: }; d82ca3d4de 2014-05-29 kinaba: rec(v2, u2); d82ca3d4de 2014-05-29 kinaba: d82ca3d4de 2014-05-29 kinaba: vector<int> memo_vu(2*N, -1), memo_uv(2*N, -1); d82ca3d4de 2014-05-29 kinaba: for(int v1=0; v1<N-1; ++v1) { d82ca3d4de 2014-05-29 kinaba: int u1 = tree1[v1]; d82ca3d4de 2014-05-29 kinaba: int s1 = sim(T1, v1, v1, u1, sub_vu, memo_vu); d82ca3d4de 2014-05-29 kinaba: int s2 = sim(T1, v1, v1, u1, sub_uv, memo_uv); d82ca3d4de 2014-05-29 kinaba: int s3 = sim(T1, v1+N, u1, v1, sub_vu, memo_vu); d82ca3d4de 2014-05-29 kinaba: int s = max(max(s1, s2), max(s3, N-s1-s2-s3)); d82ca3d4de 2014-05-29 kinaba: total += s*s; d82ca3d4de 2014-05-29 kinaba: } d82ca3d4de 2014-05-29 kinaba: } d82ca3d4de 2014-05-29 kinaba: return total; d82ca3d4de 2014-05-29 kinaba: } d82ca3d4de 2014-05-29 kinaba: d82ca3d4de 2014-05-29 kinaba: int sim(const vector<vector<pair<EID,int>>>& T1, int E, int a1, int b1, vector<bool>& sub, vector<int>& memo) d82ca3d4de 2014-05-29 kinaba: { d82ca3d4de 2014-05-29 kinaba: if(memo[E]>=0) d82ca3d4de 2014-05-29 kinaba: return memo[E]; d82ca3d4de 2014-05-29 kinaba: d82ca3d4de 2014-05-29 kinaba: int total = sub[b1]; d82ca3d4de 2014-05-29 kinaba: for(pair<EID,int> ic: T1[b1]) {EID id=ic.first; int c1=ic.second; if(c1 != a1) { d82ca3d4de 2014-05-29 kinaba: total += sim(T1, id, b1, c1, sub, memo); d82ca3d4de 2014-05-29 kinaba: }} d82ca3d4de 2014-05-29 kinaba: return memo[E] = total; d82ca3d4de 2014-05-29 kinaba: } d82ca3d4de 2014-05-29 kinaba: }; d82ca3d4de 2014-05-29 kinaba: d82ca3d4de 2014-05-29 kinaba: // BEGIN CUT HERE d82ca3d4de 2014-05-29 kinaba: #include <ctime> d82ca3d4de 2014-05-29 kinaba: double start_time; string timer() d82ca3d4de 2014-05-29 kinaba: { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } d82ca3d4de 2014-05-29 kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) d82ca3d4de 2014-05-29 kinaba: { os << "{ "; d82ca3d4de 2014-05-29 kinaba: for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) d82ca3d4de 2014-05-29 kinaba: os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } d82ca3d4de 2014-05-29 kinaba: void verify_case(const long long& Expected, const long long& Received) { d82ca3d4de 2014-05-29 kinaba: bool ok = (Expected == Received); d82ca3d4de 2014-05-29 kinaba: if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; d82ca3d4de 2014-05-29 kinaba: cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } d82ca3d4de 2014-05-29 kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); d82ca3d4de 2014-05-29 kinaba: #define END verify_case(_, TreesAnalysis().treeSimilarity(tree1, tree2));} d82ca3d4de 2014-05-29 kinaba: int main(){ d82ca3d4de 2014-05-29 kinaba: d82ca3d4de 2014-05-29 kinaba: CASE(0) d82ca3d4de 2014-05-29 kinaba: int tree1_[] = {1}; d82ca3d4de 2014-05-29 kinaba: vector <int> tree1(tree1_, tree1_+sizeof(tree1_)/sizeof(*tree1_)); d82ca3d4de 2014-05-29 kinaba: int tree2_[] = {1}; d82ca3d4de 2014-05-29 kinaba: vector <int> tree2(tree2_, tree2_+sizeof(tree2_)/sizeof(*tree2_)); d82ca3d4de 2014-05-29 kinaba: long long _ = 1LL; d82ca3d4de 2014-05-29 kinaba: END d82ca3d4de 2014-05-29 kinaba: CASE(1) d82ca3d4de 2014-05-29 kinaba: int tree1_[] = {2, 4, 1, 0}; d82ca3d4de 2014-05-29 kinaba: vector <int> tree1(tree1_, tree1_+sizeof(tree1_)/sizeof(*tree1_)); d82ca3d4de 2014-05-29 kinaba: int tree2_[] = {1, 4, 4, 4}; d82ca3d4de 2014-05-29 kinaba: vector <int> tree2(tree2_, tree2_+sizeof(tree2_)/sizeof(*tree2_)); d82ca3d4de 2014-05-29 kinaba: long long _ = 111LL; d82ca3d4de 2014-05-29 kinaba: END d82ca3d4de 2014-05-29 kinaba: CASE(2) d82ca3d4de 2014-05-29 kinaba: int tree1_[] = {1, 2, 3, 4}; d82ca3d4de 2014-05-29 kinaba: vector <int> tree1(tree1_, tree1_+sizeof(tree1_)/sizeof(*tree1_)); d82ca3d4de 2014-05-29 kinaba: int tree2_[] = {1, 2, 3, 4} d82ca3d4de 2014-05-29 kinaba: ; d82ca3d4de 2014-05-29 kinaba: vector <int> tree2(tree2_, tree2_+sizeof(tree2_)/sizeof(*tree2_)); d82ca3d4de 2014-05-29 kinaba: long long _ = 128LL; d82ca3d4de 2014-05-29 kinaba: END d82ca3d4de 2014-05-29 kinaba: CASE(3) d82ca3d4de 2014-05-29 kinaba: int tree1_[] = {2, 3, 4, 4, 5, 8, 5, 6, 10, 8}; d82ca3d4de 2014-05-29 kinaba: vector <int> tree1(tree1_, tree1_+sizeof(tree1_)/sizeof(*tree1_)); d82ca3d4de 2014-05-29 kinaba: int tree2_[] = {9, 0, 1, 0, 3, 0, 5, 0, 7, 10}; d82ca3d4de 2014-05-29 kinaba: vector <int> tree2(tree2_, tree2_+sizeof(tree2_)/sizeof(*tree2_)); d82ca3d4de 2014-05-29 kinaba: long long _ = 6306LL; d82ca3d4de 2014-05-29 kinaba: END d82ca3d4de 2014-05-29 kinaba: CASE(4) d82ca3d4de 2014-05-29 kinaba: int tree1_[] = {222, 261, 167, 133, 174, 150, 165, 311, 208, 268, 111, 222, 154, 277, 282, 201, 46, 124, 194, 331, 4, 216, 111, d82ca3d4de 2014-05-29 kinaba: 275, 72, 322, 137, 216, 241, 48, 72, 101, 232, 165, 151, 263, 139, 16, 122, 140, 84, 135, 314, 106, 309, 126, 102, d82ca3d4de 2014-05-29 kinaba: 151, 208, 27, 242, 93, 83, 314, 136, 77, 82, 215, 16, 232, 286, 156, 294, 38, 67, 204, 206, 137, 174, 282, 188, d82ca3d4de 2014-05-29 kinaba: 143, 84, 279, 236, 136, 158, 10, 65, 332, 122, 44, 329, 62, 174, 67, 102, 216, 245, 296, 287, 307, 93, 197, 169, d82ca3d4de 2014-05-29 kinaba: 268, 266, 294, 157, 277, 95, 68, 214, 135, 211, 127, 82, 108, 212, 161, 243, 212, 207, 119, 119, 158, 97, 290, 21, d82ca3d4de 2014-05-29 kinaba: 217, 230, 85, 171, 13, 138, 294, 304, 204, 318, 115, 70, 210, 195, 223, 37, 164, 149, 3, 164, 328, 316, 108, 330, d82ca3d4de 2014-05-29 kinaba: 48, 38, 324, 222, 193, 50, 41, 184, 93, 148, 41, 151, 139, 106, 301, 264, 80, 249, 110, 244, 109, 212, 223, 279, d82ca3d4de 2014-05-29 kinaba: 330, 67, 27, 301, 165, 236, 194, 3, 157, 1, 217, 311, 87, 105, 4, 286, 37, 6, 31, 111, 66, 230, 227, 244, 322, d82ca3d4de 2014-05-29 kinaba: 196, 65, 69, 305, 112, 133, 231, 68, 153, 206, 309, 248, 329, 58, 69, 69, 328, 0, 29, 233, 243, 305, 167, 80, 65, d82ca3d4de 2014-05-29 kinaba: 194, 190, 179, 142, 196, 324, 206, 134, 50, 272, 261, 10, 147, 329, 322, 14, 142, 169, 21, 296, 284, 241, 55, 304, d82ca3d4de 2014-05-29 kinaba: 150, 166, 230, 167, 304, 87, 156, 156, 97, 274, 324, 196, 101, 82, 106, 260, 242, 233, 207, 305, 10, 166, 53, 18, d82ca3d4de 2014-05-29 kinaba: 154, 233, 217, 296, 263, 168, 138, 30, 115, 135, 188, 98, 309, 292, 204, 150, 210, 332, 330, 166, 96, 70, 24, 229, d82ca3d4de 2014-05-29 kinaba: 215, 201, 285, 40, 287, 142, 68, 133, 208, 268, 161, 310, 41, 203, 73, 275, 184, 163, 227, 89, 110, 328, 108, 112, d82ca3d4de 2014-05-29 kinaba: 125, 164, 127, 179, 267, 221, 49, 139, 1, 84, 136, 38, 6, 70, 246, 243, 3, 188, 297}; d82ca3d4de 2014-05-29 kinaba: vector <int> tree1(tree1_, tree1_+sizeof(tree1_)/sizeof(*tree1_)); d82ca3d4de 2014-05-29 kinaba: int tree2_[] = {174, 262, 195, 288, 157, 278, 36, 133, 230, 273, 222, 138, 97, 23, 189, 141, 296, 55, 45, 301, 81, 199, 188, 289, d82ca3d4de 2014-05-29 kinaba: 187, 164, 113, 58, 138, 300, 289, 282, 329, 91, 130, 178, 92, 143, 48, 81, 311, 133, 151, 286, 171, 196, 199, 80, d82ca3d4de 2014-05-29 kinaba: 83, 121, 65, 151, 277, 136, 49, 111, 58, 36, 259, 14, 31, 9, 136, 181, 122, 324, 249, 114, 9, 37, 259, 242, 165, d82ca3d4de 2014-05-29 kinaba: 174, 34, 36, 298, 92, 301, 237, 178, 82, 65, 295, 110, 311, 274, 235, 68, 56, 259, 180, 195, 52, 110, 68, 140, 71, d82ca3d4de 2014-05-29 kinaba: 52, 296, 290, 115, 213, 82, 209, 209, 74, 178, 302, 131, 99, 205, 296, 309, 288, 180, 329, 71, 143, 58, 152, 273, d82ca3d4de 2014-05-29 kinaba: 196, 7, 169, 88, 231, 331, 213, 181, 80, 249, 170, 246, 16, 127, 75, 276, 332, 174, 21, 180, 163, 78, 242, 312, d82ca3d4de 2014-05-29 kinaba: 295, 199, 89, 142, 85, 195, 115, 119, 95, 94, 279, 290, 3, 33, 93, 284, 20, 47, 47, 78, 331, 271, 113, 179, 249, d82ca3d4de 2014-05-29 kinaba: 331, 92, 324, 9, 71, 232, 46, 28, 289, 80, 28, 80, 134, 20, 280, 277, 48, 205, 107, 52, 320, 4, 191, 160, 182, d82ca3d4de 2014-05-29 kinaba: 189, 227, 295, 115, 54, 195, 78, 292, 189, 273, 301, 69, 305, 36, 222, 167, 326, 106, 48, 45, 74, 61, 181, 311, d82ca3d4de 2014-05-29 kinaba: 292, 270, 201, 34, 314, 218, 214, 92, 269, 18, 37, 151, 142, 209, 11, 227, 327, 198, 28, 272, 152, 22, 47, 143, d82ca3d4de 2014-05-29 kinaba: 332, 253, 273, 35, 78, 130, 295, 223, 181, 329, 18, 238, 300, 186, 274, 99, 300, 322, 41, 185, 311, 288, 198, 2, d82ca3d4de 2014-05-29 kinaba: 37, 83, 238, 133, 122, 178, 107, 106, 66, 238, 69, 90, 38, 109, 246, 278, 288, 250, 321, 269, 130, 28, 115, 122, d82ca3d4de 2014-05-29 kinaba: 33, 185, 275, 99, 130, 99, 152, 268, 133, 249, 180, 30, 210, 201, 324, 29, 290, 143, 3, 269, 68, 106, 230, 1, d82ca3d4de 2014-05-29 kinaba: 269, 29, 120, 259, 324, 328, 23, 243, 9, 61, 14, 118, 199, 146, 237, 14}; d82ca3d4de 2014-05-29 kinaba: vector <int> tree2(tree2_, tree2_+sizeof(tree2_)/sizeof(*tree2_)); d82ca3d4de 2014-05-29 kinaba: long long _ = 11478648052LL; d82ca3d4de 2014-05-29 kinaba: END d82ca3d4de 2014-05-29 kinaba: /* d82ca3d4de 2014-05-29 kinaba: CASE(5) d82ca3d4de 2014-05-29 kinaba: int tree1_[] = ; d82ca3d4de 2014-05-29 kinaba: vector <int> tree1(tree1_, tree1_+sizeof(tree1_)/sizeof(*tree1_)); d82ca3d4de 2014-05-29 kinaba: int tree2_[] = ; d82ca3d4de 2014-05-29 kinaba: vector <int> tree2(tree2_, tree2_+sizeof(tree2_)/sizeof(*tree2_)); d82ca3d4de 2014-05-29 kinaba: long long _ = LL; d82ca3d4de 2014-05-29 kinaba: END d82ca3d4de 2014-05-29 kinaba: CASE(6) d82ca3d4de 2014-05-29 kinaba: int tree1_[] = ; d82ca3d4de 2014-05-29 kinaba: vector <int> tree1(tree1_, tree1_+sizeof(tree1_)/sizeof(*tree1_)); d82ca3d4de 2014-05-29 kinaba: int tree2_[] = ; d82ca3d4de 2014-05-29 kinaba: vector <int> tree2(tree2_, tree2_+sizeof(tree2_)/sizeof(*tree2_)); d82ca3d4de 2014-05-29 kinaba: long long _ = LL; d82ca3d4de 2014-05-29 kinaba: END d82ca3d4de 2014-05-29 kinaba: */ d82ca3d4de 2014-05-29 kinaba: } d82ca3d4de 2014-05-29 kinaba: // END CUT HERE