e73fe40bab 2015-03-09 kinaba: #include <iostream> e73fe40bab 2015-03-09 kinaba: #include <sstream> e73fe40bab 2015-03-09 kinaba: #include <iomanip> e73fe40bab 2015-03-09 kinaba: #include <vector> e73fe40bab 2015-03-09 kinaba: #include <string> e73fe40bab 2015-03-09 kinaba: #include <map> e73fe40bab 2015-03-09 kinaba: #include <set> e73fe40bab 2015-03-09 kinaba: #include <algorithm> e73fe40bab 2015-03-09 kinaba: #include <numeric> e73fe40bab 2015-03-09 kinaba: #include <iterator> e73fe40bab 2015-03-09 kinaba: #include <functional> e73fe40bab 2015-03-09 kinaba: #include <complex> e73fe40bab 2015-03-09 kinaba: #include <queue> e73fe40bab 2015-03-09 kinaba: #include <stack> e73fe40bab 2015-03-09 kinaba: #include <cmath> e73fe40bab 2015-03-09 kinaba: #include <cassert> e73fe40bab 2015-03-09 kinaba: #include <tuple> e73fe40bab 2015-03-09 kinaba: using namespace std; e73fe40bab 2015-03-09 kinaba: typedef long long LL; e73fe40bab 2015-03-09 kinaba: typedef complex<double> CMP; e73fe40bab 2015-03-09 kinaba: e73fe40bab 2015-03-09 kinaba: class TheKingsRoadsDiv1 { public: e73fe40bab 2015-03-09 kinaba: string getAnswer(int h, vector <int> a, vector <int> b) e73fe40bab 2015-03-09 kinaba: { e73fe40bab 2015-03-09 kinaba: return solve(h, a, b) ? "Correct" : "Incorrect"; e73fe40bab 2015-03-09 kinaba: } e73fe40bab 2015-03-09 kinaba: e73fe40bab 2015-03-09 kinaba: bool solve(int h, const vector<int>& a, const vector<int>& b) e73fe40bab 2015-03-09 kinaba: { e73fe40bab 2015-03-09 kinaba: // remove obvious abnormality e73fe40bab 2015-03-09 kinaba: set<pair<int,int>> e; e73fe40bab 2015-03-09 kinaba: for(int i=0; i<a.size(); ++i) e73fe40bab 2015-03-09 kinaba: if(a[i] != b[i]) e73fe40bab 2015-03-09 kinaba: e.emplace(min(a[i]-1, b[i]-1), max(a[i]-1,b[i]-1)); // I love 0-based indexing. e73fe40bab 2015-03-09 kinaba: e73fe40bab 2015-03-09 kinaba: if(e.size()+3 < a.size()) e73fe40bab 2015-03-09 kinaba: return false; e73fe40bab 2015-03-09 kinaba: e73fe40bab 2015-03-09 kinaba: const int added = e.size() - ((1<<h)-2); e73fe40bab 2015-03-09 kinaba: const int N = (1<<h)-1; e73fe40bab 2015-03-09 kinaba: vector<vector<int>> g(N); e73fe40bab 2015-03-09 kinaba: for(auto ab: e) { e73fe40bab 2015-03-09 kinaba: g[ab.first].emplace_back(ab.second); e73fe40bab 2015-03-09 kinaba: g[ab.second].emplace_back(ab.first); e73fe40bab 2015-03-09 kinaba: } e73fe40bab 2015-03-09 kinaba: e73fe40bab 2015-03-09 kinaba: set<pair<int,int>> susp_edges = e; e73fe40bab 2015-03-09 kinaba: e73fe40bab 2015-03-09 kinaba: vector<int> det_height(N, 0); e73fe40bab 2015-03-09 kinaba: vector<vector<int>> det_child(N); e73fe40bab 2015-03-09 kinaba: vector<int> det_parent(N, -1); e73fe40bab 2015-03-09 kinaba: vector<int> Q; e73fe40bab 2015-03-09 kinaba: for(int v=0; v<N; ++v) { e73fe40bab 2015-03-09 kinaba: if(g[v].empty()) e73fe40bab 2015-03-09 kinaba: return false; e73fe40bab 2015-03-09 kinaba: if(g[v].size() == 1) { e73fe40bab 2015-03-09 kinaba: det_height[v] = 1; e73fe40bab 2015-03-09 kinaba: Q.emplace_back(g[v].front()); e73fe40bab 2015-03-09 kinaba: } e73fe40bab 2015-03-09 kinaba: } e73fe40bab 2015-03-09 kinaba: e73fe40bab 2015-03-09 kinaba: for(int dh=2; dh<=h; ++dh) { e73fe40bab 2015-03-09 kinaba: vector<int> Q2; e73fe40bab 2015-03-09 kinaba: for(int v: Q) { e73fe40bab 2015-03-09 kinaba: if(det_height[v] == dh) e73fe40bab 2015-03-09 kinaba: continue; e73fe40bab 2015-03-09 kinaba: else if(det_height[v] == 0) { e73fe40bab 2015-03-09 kinaba: det_height[v] = dh; e73fe40bab 2015-03-09 kinaba: vector<int> cand; e73fe40bab 2015-03-09 kinaba: for(int u: g[v]) e73fe40bab 2015-03-09 kinaba: if(det_height[u] == 0) e73fe40bab 2015-03-09 kinaba: cand.push_back(u); e73fe40bab 2015-03-09 kinaba: if(dh==h) e73fe40bab 2015-03-09 kinaba: det_parent[v] = -2; e73fe40bab 2015-03-09 kinaba: if(cand.size() == 1 && dh<h) { e73fe40bab 2015-03-09 kinaba: int u = cand.front(); e73fe40bab 2015-03-09 kinaba: Q2.push_back(u); e73fe40bab 2015-03-09 kinaba: det_child[u].emplace_back(v); e73fe40bab 2015-03-09 kinaba: det_parent[v] = u; e73fe40bab 2015-03-09 kinaba: if(det_child[u].size() > 2) e73fe40bab 2015-03-09 kinaba: return false; e73fe40bab 2015-03-09 kinaba: susp_edges.erase(make_pair(min(v,u), max(v,u))); e73fe40bab 2015-03-09 kinaba: } e73fe40bab 2015-03-09 kinaba: } else { e73fe40bab 2015-03-09 kinaba: return false; e73fe40bab 2015-03-09 kinaba: } e73fe40bab 2015-03-09 kinaba: } e73fe40bab 2015-03-09 kinaba: Q.swap(Q2); e73fe40bab 2015-03-09 kinaba: } e73fe40bab 2015-03-09 kinaba: e73fe40bab 2015-03-09 kinaba: queue<int> QQ; e73fe40bab 2015-03-09 kinaba: for(int v=0; v<N; ++v) e73fe40bab 2015-03-09 kinaba: QQ.push(v); e73fe40bab 2015-03-09 kinaba: while(!QQ.empty()){ e73fe40bab 2015-03-09 kinaba: int v = QQ.front(); QQ.pop(); e73fe40bab 2015-03-09 kinaba: if(det_height[v]==0 || det_parent[v]!=-1) e73fe40bab 2015-03-09 kinaba: continue; e73fe40bab 2015-03-09 kinaba: e73fe40bab 2015-03-09 kinaba: vector<int> cand; e73fe40bab 2015-03-09 kinaba: for(int u: g[v]) e73fe40bab 2015-03-09 kinaba: if(det_height[u] == det_height[v]+1 || det_height[u]==0) e73fe40bab 2015-03-09 kinaba: cand.push_back(u); e73fe40bab 2015-03-09 kinaba: if(cand.size() == 1) { e73fe40bab 2015-03-09 kinaba: int u = cand.front(); e73fe40bab 2015-03-09 kinaba: QQ.push(u); e73fe40bab 2015-03-09 kinaba: det_child[u].emplace_back(v); e73fe40bab 2015-03-09 kinaba: det_parent[v] = u; e73fe40bab 2015-03-09 kinaba: if(det_child[u].size() > 2) e73fe40bab 2015-03-09 kinaba: return false; e73fe40bab 2015-03-09 kinaba: susp_edges.erase(make_pair(min(v,u), max(v,u))); e73fe40bab 2015-03-09 kinaba: } e73fe40bab 2015-03-09 kinaba: } e73fe40bab 2015-03-09 kinaba: e73fe40bab 2015-03-09 kinaba: int cnt = 0; e73fe40bab 2015-03-09 kinaba: for(int dh: det_height) e73fe40bab 2015-03-09 kinaba: if(dh) e73fe40bab 2015-03-09 kinaba: ++cnt; e73fe40bab 2015-03-09 kinaba: cerr << cnt << " / " << N << " @ " << susp_edges.size() << endl; e73fe40bab 2015-03-09 kinaba: return susp_edges.size() == added; e73fe40bab 2015-03-09 kinaba: } e73fe40bab 2015-03-09 kinaba: }; e73fe40bab 2015-03-09 kinaba: e73fe40bab 2015-03-09 kinaba: // BEGIN CUT HERE e73fe40bab 2015-03-09 kinaba: #include <ctime> e73fe40bab 2015-03-09 kinaba: double start_time; string timer() e73fe40bab 2015-03-09 kinaba: { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } e73fe40bab 2015-03-09 kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) e73fe40bab 2015-03-09 kinaba: { os << "{ "; e73fe40bab 2015-03-09 kinaba: for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) e73fe40bab 2015-03-09 kinaba: os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } e73fe40bab 2015-03-09 kinaba: void verify_case(const string& Expected, const string& Received) { e73fe40bab 2015-03-09 kinaba: bool ok = (Expected == Received); e73fe40bab 2015-03-09 kinaba: if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; e73fe40bab 2015-03-09 kinaba: cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } e73fe40bab 2015-03-09 kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); e73fe40bab 2015-03-09 kinaba: #define END verify_case(_, TheKingsRoadsDiv1().getAnswer(h, a, b));} e73fe40bab 2015-03-09 kinaba: int main(){ e73fe40bab 2015-03-09 kinaba: e73fe40bab 2015-03-09 kinaba: CASE(0) e73fe40bab 2015-03-09 kinaba: int h = 3; e73fe40bab 2015-03-09 kinaba: int a_[] = {1, 3, 2, 2, 3, 7, 1, 5, 4}; e73fe40bab 2015-03-09 kinaba: vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_)); e73fe40bab 2015-03-09 kinaba: int b_[] = {6, 5, 4, 7, 4, 3, 3, 1, 7}; e73fe40bab 2015-03-09 kinaba: vector <int> b(b_, b_+sizeof(b_)/sizeof(*b_)); e73fe40bab 2015-03-09 kinaba: string _ = "Correct"; e73fe40bab 2015-03-09 kinaba: END e73fe40bab 2015-03-09 kinaba: CASE(1) e73fe40bab 2015-03-09 kinaba: int h = 2; e73fe40bab 2015-03-09 kinaba: int a_[] = {1, 2, 1, 3, 3}; e73fe40bab 2015-03-09 kinaba: vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_)); e73fe40bab 2015-03-09 kinaba: int b_[] = {2, 1, 2, 3, 3}; e73fe40bab 2015-03-09 kinaba: vector <int> b(b_, b_+sizeof(b_)/sizeof(*b_)); e73fe40bab 2015-03-09 kinaba: string _ = "Incorrect"; e73fe40bab 2015-03-09 kinaba: END e73fe40bab 2015-03-09 kinaba: CASE(2) e73fe40bab 2015-03-09 kinaba: int h = 3; e73fe40bab 2015-03-09 kinaba: int a_[] = {1, 3, 2, 2, 6, 6, 4, 4, 7}; e73fe40bab 2015-03-09 kinaba: vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_)); e73fe40bab 2015-03-09 kinaba: int b_[] = {2, 1, 4, 5, 4, 4, 7, 7, 6}; e73fe40bab 2015-03-09 kinaba: vector <int> b(b_, b_+sizeof(b_)/sizeof(*b_)); e73fe40bab 2015-03-09 kinaba: string _ = "Incorrect"; e73fe40bab 2015-03-09 kinaba: END e73fe40bab 2015-03-09 kinaba: CASE(3) e73fe40bab 2015-03-09 kinaba: int h = 2; e73fe40bab 2015-03-09 kinaba: int a_[] = {1, 2, 2, 1, 1}; e73fe40bab 2015-03-09 kinaba: vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_)); e73fe40bab 2015-03-09 kinaba: int b_[] = {1, 2, 2, 1, 2}; e73fe40bab 2015-03-09 kinaba: vector <int> b(b_, b_+sizeof(b_)/sizeof(*b_)); e73fe40bab 2015-03-09 kinaba: string _ = "Incorrect"; e73fe40bab 2015-03-09 kinaba: END e73fe40bab 2015-03-09 kinaba: CASE(4) e73fe40bab 2015-03-09 kinaba: int h = 5; e73fe40bab 2015-03-09 kinaba: int a_[] = {6, 15, 29, 28, 7, 13, 13, 23, 28, 13, 30, 27, 14, 4, 14, 19, 27, 20, 20, 19, 10, 15, 7, 7, 19, 29, 4, 24, 10, 23, 30, 6, 24}; e73fe40bab 2015-03-09 kinaba: vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_)); e73fe40bab 2015-03-09 kinaba: int b_[] = {9, 22, 30, 20, 26, 25, 8, 7, 24, 21, 27, 31, 4, 28, 29, 6, 16, 1, 17, 10, 3, 12, 30, 18, 14, 23, 19, 21, 5, 13, 15, 2, 11}; e73fe40bab 2015-03-09 kinaba: vector <int> b(b_, b_+sizeof(b_)/sizeof(*b_)); e73fe40bab 2015-03-09 kinaba: string _ = "Correct"; e73fe40bab 2015-03-09 kinaba: END e73fe40bab 2015-03-09 kinaba: CASE(5) e73fe40bab 2015-03-09 kinaba: int h = 2; e73fe40bab 2015-03-09 kinaba: int a_[] = {1,1,1,2,1}; e73fe40bab 2015-03-09 kinaba: vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_)); e73fe40bab 2015-03-09 kinaba: int b_[] = {2,3,1,2,2}; e73fe40bab 2015-03-09 kinaba: vector <int> b(b_, b_+sizeof(b_)/sizeof(*b_)); e73fe40bab 2015-03-09 kinaba: string _ = "Correct"; e73fe40bab 2015-03-09 kinaba: END e73fe40bab 2015-03-09 kinaba: /* e73fe40bab 2015-03-09 kinaba: CASE(6) e73fe40bab 2015-03-09 kinaba: int h = ; e73fe40bab 2015-03-09 kinaba: int a_[] = ; e73fe40bab 2015-03-09 kinaba: vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_)); e73fe40bab 2015-03-09 kinaba: int b_[] = ; e73fe40bab 2015-03-09 kinaba: vector <int> b(b_, b_+sizeof(b_)/sizeof(*b_)); e73fe40bab 2015-03-09 kinaba: string _ = ; e73fe40bab 2015-03-09 kinaba: END e73fe40bab 2015-03-09 kinaba: CASE(7) e73fe40bab 2015-03-09 kinaba: int h = ; e73fe40bab 2015-03-09 kinaba: int a_[] = ; e73fe40bab 2015-03-09 kinaba: vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_)); e73fe40bab 2015-03-09 kinaba: int b_[] = ; e73fe40bab 2015-03-09 kinaba: vector <int> b(b_, b_+sizeof(b_)/sizeof(*b_)); e73fe40bab 2015-03-09 kinaba: string _ = ; e73fe40bab 2015-03-09 kinaba: END e73fe40bab 2015-03-09 kinaba: */ e73fe40bab 2015-03-09 kinaba: } e73fe40bab 2015-03-09 kinaba: // END CUT HERE