e3362a9488 2014-05-10 kinaba: #include <iostream> e3362a9488 2014-05-10 kinaba: #include <sstream> e3362a9488 2014-05-10 kinaba: #include <iomanip> e3362a9488 2014-05-10 kinaba: #include <vector> e3362a9488 2014-05-10 kinaba: #include <string> e3362a9488 2014-05-10 kinaba: #include <map> e3362a9488 2014-05-10 kinaba: #include <set> e3362a9488 2014-05-10 kinaba: #include <algorithm> e3362a9488 2014-05-10 kinaba: #include <numeric> e3362a9488 2014-05-10 kinaba: #include <iterator> e3362a9488 2014-05-10 kinaba: #include <functional> e3362a9488 2014-05-10 kinaba: #include <complex> e3362a9488 2014-05-10 kinaba: #include <queue> e3362a9488 2014-05-10 kinaba: #include <stack> e3362a9488 2014-05-10 kinaba: #include <cmath> e3362a9488 2014-05-10 kinaba: #include <cassert> e3362a9488 2014-05-10 kinaba: #include <tuple> e3362a9488 2014-05-10 kinaba: using namespace std; e3362a9488 2014-05-10 kinaba: typedef long long LL; e3362a9488 2014-05-10 kinaba: typedef complex<double> CMP; e3362a9488 2014-05-10 kinaba: e3362a9488 2014-05-10 kinaba: class Family { public: e3362a9488 2014-05-10 kinaba: string isFamily(vector <int> parent1, vector <int> parent2) e3362a9488 2014-05-10 kinaba: { e3362a9488 2014-05-10 kinaba: return solve(parent1, parent2) ? "Possible" : "Impossible"; e3362a9488 2014-05-10 kinaba: } e3362a9488 2014-05-10 kinaba: e3362a9488 2014-05-10 kinaba: bool solve(vector <int> parent1, vector <int> parent2) e3362a9488 2014-05-10 kinaba: { e3362a9488 2014-05-10 kinaba: const int N = parent1.size(); e3362a9488 2014-05-10 kinaba: e3362a9488 2014-05-10 kinaba: map<int, vector<int>> diff; e3362a9488 2014-05-10 kinaba: for(int i=0; i<N; ++i) e3362a9488 2014-05-10 kinaba: { e3362a9488 2014-05-10 kinaba: int a = parent1[i]; e3362a9488 2014-05-10 kinaba: int b = parent2[i]; e3362a9488 2014-05-10 kinaba: if(a != -1) { e3362a9488 2014-05-10 kinaba: assert(b != -1); e3362a9488 2014-05-10 kinaba: diff[a].push_back(b); e3362a9488 2014-05-10 kinaba: diff[b].push_back(a); e3362a9488 2014-05-10 kinaba: } e3362a9488 2014-05-10 kinaba: } e3362a9488 2014-05-10 kinaba: e3362a9488 2014-05-10 kinaba: bool ok = true; e3362a9488 2014-05-10 kinaba: e3362a9488 2014-05-10 kinaba: enum {Unk, Ma=1, Fe=2}; e3362a9488 2014-05-10 kinaba: vector<int> gender(N, Unk); e3362a9488 2014-05-10 kinaba: function<void(int)> rec_fill; rec_fill = [&](int p) { e3362a9488 2014-05-10 kinaba: for(int q : diff[p]) e3362a9488 2014-05-10 kinaba: if(gender[q] == Unk) { e3362a9488 2014-05-10 kinaba: gender[q] = 3 - gender[p]; e3362a9488 2014-05-10 kinaba: rec_fill(q); e3362a9488 2014-05-10 kinaba: } else if(gender[q] == gender[p]) { e3362a9488 2014-05-10 kinaba: ok = false; e3362a9488 2014-05-10 kinaba: return; e3362a9488 2014-05-10 kinaba: } e3362a9488 2014-05-10 kinaba: }; e3362a9488 2014-05-10 kinaba: e3362a9488 2014-05-10 kinaba: for(int p=0; p<N; ++p) e3362a9488 2014-05-10 kinaba: { e3362a9488 2014-05-10 kinaba: if(gender[p] == Unk) { e3362a9488 2014-05-10 kinaba: gender[p] = Ma; e3362a9488 2014-05-10 kinaba: rec_fill(p); e3362a9488 2014-05-10 kinaba: if(!ok) e3362a9488 2014-05-10 kinaba: return ok; e3362a9488 2014-05-10 kinaba: } e3362a9488 2014-05-10 kinaba: } e3362a9488 2014-05-10 kinaba: return ok; e3362a9488 2014-05-10 kinaba: } e3362a9488 2014-05-10 kinaba: }; e3362a9488 2014-05-10 kinaba: e3362a9488 2014-05-10 kinaba: // BEGIN CUT HERE e3362a9488 2014-05-10 kinaba: #include <ctime> e3362a9488 2014-05-10 kinaba: double start_time; string timer() e3362a9488 2014-05-10 kinaba: { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } e3362a9488 2014-05-10 kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) e3362a9488 2014-05-10 kinaba: { os << "{ "; e3362a9488 2014-05-10 kinaba: for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) e3362a9488 2014-05-10 kinaba: os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } e3362a9488 2014-05-10 kinaba: void verify_case(const string& Expected, const string& Received) { e3362a9488 2014-05-10 kinaba: bool ok = (Expected == Received); e3362a9488 2014-05-10 kinaba: if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; e3362a9488 2014-05-10 kinaba: cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } e3362a9488 2014-05-10 kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); e3362a9488 2014-05-10 kinaba: #define END verify_case(_, Family().isFamily(parent1, parent2));} e3362a9488 2014-05-10 kinaba: int main(){ e3362a9488 2014-05-10 kinaba: e3362a9488 2014-05-10 kinaba: CASE(0) e3362a9488 2014-05-10 kinaba: int parent1_[] = {-1,-1,0}; e3362a9488 2014-05-10 kinaba: vector <int> parent1(parent1_, parent1_+sizeof(parent1_)/sizeof(*parent1_)); e3362a9488 2014-05-10 kinaba: int parent2_[] = {-1,-1,1}; e3362a9488 2014-05-10 kinaba: vector <int> parent2(parent2_, parent2_+sizeof(parent2_)/sizeof(*parent2_)); e3362a9488 2014-05-10 kinaba: string _ = "Possible"; e3362a9488 2014-05-10 kinaba: END e3362a9488 2014-05-10 kinaba: CASE(1) e3362a9488 2014-05-10 kinaba: int parent1_[] = {-1,-1,-1,-1,-1}; e3362a9488 2014-05-10 kinaba: vector <int> parent1(parent1_, parent1_+sizeof(parent1_)/sizeof(*parent1_)); e3362a9488 2014-05-10 kinaba: int parent2_[] = {-1,-1,-1,-1,-1}; e3362a9488 2014-05-10 kinaba: vector <int> parent2(parent2_, parent2_+sizeof(parent2_)/sizeof(*parent2_)); e3362a9488 2014-05-10 kinaba: string _ = "Possible"; e3362a9488 2014-05-10 kinaba: END e3362a9488 2014-05-10 kinaba: CASE(2) e3362a9488 2014-05-10 kinaba: int parent1_[] = {-1,-1,0,0,1}; e3362a9488 2014-05-10 kinaba: vector <int> parent1(parent1_, parent1_+sizeof(parent1_)/sizeof(*parent1_)); e3362a9488 2014-05-10 kinaba: int parent2_[] = {-1,-1,1,2,2}; e3362a9488 2014-05-10 kinaba: vector <int> parent2(parent2_, parent2_+sizeof(parent2_)/sizeof(*parent2_)); e3362a9488 2014-05-10 kinaba: string _ = "Impossible"; e3362a9488 2014-05-10 kinaba: END e3362a9488 2014-05-10 kinaba: CASE(3) e3362a9488 2014-05-10 kinaba: int parent1_[] = {-1,-1,-1,-1,1,-1,0,5,6,-1,0,3,8,6} e3362a9488 2014-05-10 kinaba: ; e3362a9488 2014-05-10 kinaba: vector <int> parent1(parent1_, parent1_+sizeof(parent1_)/sizeof(*parent1_)); e3362a9488 2014-05-10 kinaba: int parent2_[] = {-1,-1,-1,-1,3,-1,4,6,5,-1,5,4,6,1} e3362a9488 2014-05-10 kinaba: ; e3362a9488 2014-05-10 kinaba: vector <int> parent2(parent2_, parent2_+sizeof(parent2_)/sizeof(*parent2_)); e3362a9488 2014-05-10 kinaba: string _ = "Possible"; e3362a9488 2014-05-10 kinaba: END e3362a9488 2014-05-10 kinaba: CASE(4) e3362a9488 2014-05-10 kinaba: int parent1_[] = {-1,-1,-1,2,2,-1,5,6,4,6,2,1,8,0,2,4,6,9,-1,16,-1,11}; e3362a9488 2014-05-10 kinaba: vector <int> parent1(parent1_, parent1_+sizeof(parent1_)/sizeof(*parent1_)); e3362a9488 2014-05-10 kinaba: int parent2_[] = {-1,-1,-1,1,0,-1,1,4,2,0,4,8,2,3,0,5,14,14,-1,7,-1,13}; e3362a9488 2014-05-10 kinaba: vector <int> parent2(parent2_, parent2_+sizeof(parent2_)/sizeof(*parent2_)); e3362a9488 2014-05-10 kinaba: string _ = "Impossible"; e3362a9488 2014-05-10 kinaba: END e3362a9488 2014-05-10 kinaba: /* e3362a9488 2014-05-10 kinaba: CASE(5) e3362a9488 2014-05-10 kinaba: int parent1_[] = ; e3362a9488 2014-05-10 kinaba: vector <int> parent1(parent1_, parent1_+sizeof(parent1_)/sizeof(*parent1_)); e3362a9488 2014-05-10 kinaba: int parent2_[] = ; e3362a9488 2014-05-10 kinaba: vector <int> parent2(parent2_, parent2_+sizeof(parent2_)/sizeof(*parent2_)); e3362a9488 2014-05-10 kinaba: string _ = ; e3362a9488 2014-05-10 kinaba: END e3362a9488 2014-05-10 kinaba: CASE(6) e3362a9488 2014-05-10 kinaba: int parent1_[] = ; e3362a9488 2014-05-10 kinaba: vector <int> parent1(parent1_, parent1_+sizeof(parent1_)/sizeof(*parent1_)); e3362a9488 2014-05-10 kinaba: int parent2_[] = ; e3362a9488 2014-05-10 kinaba: vector <int> parent2(parent2_, parent2_+sizeof(parent2_)/sizeof(*parent2_)); e3362a9488 2014-05-10 kinaba: string _ = ; e3362a9488 2014-05-10 kinaba: END e3362a9488 2014-05-10 kinaba: */ e3362a9488 2014-05-10 kinaba: } e3362a9488 2014-05-10 kinaba: // END CUT HERE