SRM 559 500

HatRack.cpp

#include <functional>
#include <algorithm>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <numeric>
#include <cstring>
#include <climits>
#include <cassert>
#include <complex>
#include <cstdio>
#include <string>
#include <vector>
#include <bitset>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <list>
#include <set>
#include <map>

using namespace std;

#define REP(I, N) for (int I=0;I<int(N);++I)
#define FOR(I, A, B) for (int I=int(A);I<int(B);++I)
#define DWN(I, B, A) for (int I=int(B-1);I>=int(A);--I)
#define REP_1(i, n) for (int i=1;i<=int(n);++i)
#define FOR_1(i, a, b) for (int i=int(a);i<=int(b);++i)
#define DWN_1(i, b, a) for (int i=int(b);i>=int(a);--i)
#define ECH(it, A) for (typeof(A.begin()) it=A.begin(); it != A.end(); ++it)

#define ALL(A) A.begin(), A.end()
#define CLR(A) A.clear()
#define CPY(A, B) memcpy(A, B, sizeof(A))
#define INS(A, P, B) A.insert(A.begin() + P, B)
#define ERS(A, P) A.erase(A.begin() + P)
#define SRT(A) sort(ALL(A))
#define SZ(A) int(A.size())
#define PB push_back
#define MP(A, B) make_pair(A, B)

typedef long long LL;
typedef double DB;
typedef vector<int> VI;

template<class T> inline void RST(T &A){memset(A, 0, sizeof(A));}
template<class T> inline void FLC(T &A, int x){memset(A, x, sizeof(A));}

template<class T> inline void checkMin(T &a, T b){if (b<a) a=b;}
template<class T> inline void checkMax(T &a, T b){if (b>a) a=b;}

const int MOD = 1000000007;
const int INF = 0x3f3f3f3f;

/* -- Start from here -- */

const int N = 52;
VI adj[N]; LL dp[N][N];
int n;

#define lx (x<<1)
#define rx (lx|1)
LL f(int u, int p = 0, int x = 1){

    if (x > n) return 0;

    LL &res = dp[u][x]; if (res == -1){
        res = 0; VI c; REP(i, SZ(adj[u])) if (adj[u][i] != p) c.PB(adj[u][i]);
        if (x>n/2) res = !SZ(c); // suppose to be a leaf ...
        else if (!(n&1) &&  x==n/2) res = SZ(c) == 1; // suppose to have one child .. .
        else if (SZ(c) == 2){
            res = f(c[0],u,lx)*f(c[1],u,rx) + f(c[1],u,lx)*f(c[0],u,rx);
        }
    }
    return res;
}

class HatRack {
public:
    long long countWays(vector <int> knob1, vector <int> knob2) {

        n = SZ(knob1) + 1; REP_1(i, n) CLR(adj[i]);

        REP(i, SZ(knob1)){
            int x = knob1[i], y = knob2[i];
            adj[x].PB(y), adj[y].PB(x);
        }

        LL res = 0; REP_1(i, n){
            FLC(dp, -1);
            res += f(i);
        }
        return res;
    }
};


// BEGIN CUT HERE
namespace moj_harness {
	int run_test_case(int);
	void run_test(int casenum = -1, bool quiet = false) {
		if (casenum != -1) {
			if (run_test_case(casenum) == -1 && !quiet) {
				cerr << "Illegal input! Test case " << casenum << " does not exist." << endl;
			}
			return;
		}

		int correct = 0, total = 0;
		for (int i=0;; ++i) {
			int x = run_test_case(i);
			if (x == -1) {
				if (i >= 100) break;
				continue;
			}
			correct += x;
			++total;
		}

		if (total == 0) {
			cerr << "No test cases run." << endl;
		} else if (correct < total) {
			cerr << "Some cases FAILED (passed " << correct << " of " << total << ")." << endl;
		} else {
			cerr << "All " << total << " tests passed!" << endl;
		}
	}

	int verify_case(int casenum, const long long &expected, const long long &received, clock_t elapsed) {
		cerr << "Example " << casenum << "... ";

		string verdict;
		vector<string> info;
		char buf[100];

		if (elapsed > CLOCKS_PER_SEC / 200) {
			sprintf(buf, "time %.2fs", elapsed * (1.0/CLOCKS_PER_SEC));
			info.push_back(buf);
		}

		if (expected == received) {
			verdict = "PASSED";
		} else {
			verdict = "FAILED";
		}

		cerr << verdict;
		if (!info.empty()) {
			cerr << " (";
			for (int i=0; i<(int)info.size(); ++i) {
				if (i > 0) cerr << ", ";
				cerr << info[i];
			}
			cerr << ")";
		}
		cerr << endl;

		if (verdict == "FAILED") {
			cerr << "    Expected: " << expected << endl;
			cerr << "    Received: " << received << endl;
		}

		return verdict == "PASSED";
	}

	int run_test_case(int casenum) {
		switch (casenum) {
		case 0: {
			int knob1[]               = {1};
			int knob2[]               = {2};
			long long expected__      = 2;

			clock_t start__           = clock();
			long long received__      = HatRack().countWays(vector <int>(knob1, knob1 + (sizeof knob1 / sizeof knob1[0])), vector <int>(knob2, knob2 + (sizeof knob2 / sizeof knob2[0])));
			return verify_case(casenum, expected__, received__, clock()-start__);
		}
		case 1: {
			int knob1[]               = {1,1};
			int knob2[]               = {2,3};
			long long expected__      = 2;

			clock_t start__           = clock();
			long long received__      = HatRack().countWays(vector <int>(knob1, knob1 + (sizeof knob1 / sizeof knob1[0])), vector <int>(knob2, knob2 + (sizeof knob2 / sizeof knob2[0])));
			return verify_case(casenum, expected__, received__, clock()-start__);
		}
		case 2: {
			int knob1[]               = {1,1,1,1};
			int knob2[]               = {2,3,4,5};
			long long expected__      = 0;

			clock_t start__           = clock();
			long long received__      = HatRack().countWays(vector <int>(knob1, knob1 + (sizeof knob1 / sizeof knob1[0])), vector <int>(knob2, knob2 + (sizeof knob2 / sizeof knob2[0])));
			return verify_case(casenum, expected__, received__, clock()-start__);
		}
		case 3: {
			int knob1[]               = {6,6,6,4,1};
			int knob2[]               = {1,2,4,5,3};
			long long expected__      = 0;

			clock_t start__           = clock();
			long long received__      = HatRack().countWays(vector <int>(knob1, knob1 + (sizeof knob1 / sizeof knob1[0])), vector <int>(knob2, knob2 + (sizeof knob2 / sizeof knob2[0])));
			return verify_case(casenum, expected__, received__, clock()-start__);
		}
		case 4: {
			int knob1[]               = {1,1,2,2,11,11,8,8,3,3,4,4,5};
			int knob2[]               = {2,3,11,8,12,13,9,10,4,5,7,6,14};
			long long expected__      = 16;

			clock_t start__           = clock();
			long long received__      = HatRack().countWays(vector <int>(knob1, knob1 + (sizeof knob1 / sizeof knob1[0])), vector <int>(knob2, knob2 + (sizeof knob2 / sizeof knob2[0])));
			return verify_case(casenum, expected__, received__, clock()-start__);
		}
		case 5: {
			int knob1[]               = {1,2,3,4,5,6,7,8,9};
			int knob2[]               = {2,3,4,5,6,7,8,9,10};
			long long expected__      = 0;

			clock_t start__           = clock();
			long long received__      = HatRack().countWays(vector <int>(knob1, knob1 + (sizeof knob1 / sizeof knob1[0])), vector <int>(knob2, knob2 + (sizeof knob2 / sizeof knob2[0])));
			return verify_case(casenum, expected__, received__, clock()-start__);
		}

		// custom cases

/*      case 6: {
			int knob1[]               = ;
			int knob2[]               = ;
			long long expected__      = ;

			clock_t start__           = clock();
			long long received__      = HatRack().countWays(vector <int>(knob1, knob1 + (sizeof knob1 / sizeof knob1[0])), vector <int>(knob2, knob2 + (sizeof knob2 / sizeof knob2[0])));
			return verify_case(casenum, expected__, received__, clock()-start__);
		}*/
/*      case 7: {
			int knob1[]               = ;
			int knob2[]               = ;
			long long expected__      = ;

			clock_t start__           = clock();
			long long received__      = HatRack().countWays(vector <int>(knob1, knob1 + (sizeof knob1 / sizeof knob1[0])), vector <int>(knob2, knob2 + (sizeof knob2 / sizeof knob2[0])));
			return verify_case(casenum, expected__, received__, clock()-start__);
		}*/
/*      case 8: {
			int knob1[]               = ;
			int knob2[]               = ;
			long long expected__      = ;

			clock_t start__           = clock();
			long long received__      = HatRack().countWays(vector <int>(knob1, knob1 + (sizeof knob1 / sizeof knob1[0])), vector <int>(knob2, knob2 + (sizeof knob2 / sizeof knob2[0])));
			return verify_case(casenum, expected__, received__, clock()-start__);
		}*/
		default:
			return -1;
		}
	}
}

int main(int argc, char *argv[]) {
	if (argc == 1) {
		moj_harness::run_test();
	} else {
		for (int i=1; i<argc; ++i)
			moj_harness::run_test(atoi(argv[i]));
	}
}
// END CUT HERE