fork download
copy 
  1. /*
  2. written by- Piyush Golani
  3. language- c++
  4. country- India
  5. College- N.I.T Jamshedpur
  6. */
  7. #include <cmath>
  8. #include <ctime>
  9. #include <iostream>
  10. #include <string>
  11. #include <vector>
  12. #include<cstdio>
  13. #include<sstream>
  14. #include<algorithm>
  15. #include<cstdlib>
  16. #include<cstring>
  17. #include<map>
  18. #include<set>
  19. #include<queue>
  20. #include<cctype>
  21. using namespace std;
  22. #define pb push_back
  23. #define all(s) s.begin(),s.end()
  24. #define f(i,a,b) for(int i=a;i<b;i++)
  25. #define F(i,a,b) for(int i=a;i>=b;i--)
  26. #define PI 3.1415926535897932384626433832795
  27. #define INF 2000000000
  28. #define BIG_INF 7000000000000000000LL
  29. #define mp make_pair
  30. #define eps 1e-9
  31. #define si(n) scanf("%d",&n)
  32. #define sll(n) scanf("%lld",&n)
  33. #define mod 1000000007
  34. #define mm 10000000
  35.  
  36. typedef long long LL;
  37.  
  38.  
  39. string inttostring(int n)
  40. {
  41.     stringstream a;
  42.     a<<n;
  43.     return a.str();
  44. }
  45.  
  46. int stringtoint(string A)
  47. {
  48.     istringstream a(A);
  49.     int p;
  50.     a>>p;
  51.     return p;
  52. }
  53.  
  54. //////////////////////////////////////////////////////
  55.  
  56. class CentaurCompanyDiv2 {
  57. public:
  58.     int n;
  59.     vector<int> G[52];
  60.     int dfs(vector<int> a,vector<int> b,int cur,int par)
  61.     {
  62.         int x=cur,y;
  63.         f(i,0,n)
  64.         {
  65.             if(a[i]-1==cur || b[i]-1==cur)
  66.             {
  67.                 if(a[i]-1==cur)
  68.                 {
  69.                     y=b[i]-1;
  70.                 }
  71.                 else y=a[i]-1;
  72.                 if(y!=par)
  73.                 {
  74.                     G[x].pb(y);
  75.                     dfs(a,b,y,x);
  76.                 }
  77.  
  78.             }
  79.         }
  80.         return 0;
  81.     }
  82.     LL dp[2][52];
  83.     LL doit(int p,int root)
  84.     {
  85.         LL &res=dp[p][root];
  86.         if(res>-1) return res;
  87.         res=0;
  88.         if(p==0)
  89.         {
  90.             res=doit(1,root);
  91.             f(i,0,G[root].size()) res+=doit(0,G[root][i]);
  92.         }
  93.         else
  94.         {
  95.             res=1;
  96.             f(i,0,G[root].size())
  97.             {
  98.                 LL p=doit(1,G[root][i]);
  99.                 res*=(1+p);
  100.             }
  101.         }
  102.         return res;
  103.     }
  104.    long long count( vector <int> a, vector <int> b ) {
  105.     n=a.size();
  106.     memset(dp,-1,sizeof(dp));
  107.     dfs(a,b,0,-1);
  108.     return doit(0,0)+1;
  109.    }
  110. };
  111.  
  112. // BEGIN CUT HERE
  113. namespace moj_harness {
  114.     int run_test_case(int);
  115. 	void run_test(int casenum = -1, bool quiet = false) {
  116. 		if (casenum != -1) {
  117. 			if (run_test_case(casenum) == -1 && !quiet) {
  118. 				cerr << "Illegal input! Test case " << casenum << " does not exist." << endl;
  119. 			}
  120. 			return;
  121. 		}
  122.  
  123. 		int correct = 0, total = 0;
  124. 		for (int i=0;; ++i) {
  125. 			int x = run_test_case(i);
  126. 			if (x == -1) {
  127. 				if (i >= 100) break;
  128. 				continue;
  129. 			}
  130. 			correct += x;
  131. 			++total;
  132. 		}
  133.  
  134. 		if (total == 0) {
  135. 			cerr << "No test cases run." << endl;
  136. 		} else if (correct < total) {
  137. 			cerr << "Some cases FAILED (passed " << correct << " of " << total << ")." << endl;
  138. 		} else {
  139. 			cerr << "All " << total << " tests passed!" << endl;
  140. 		}
  141. 	}
  142.  
  143. 	int verify_case(int casenum, const long long &expected, const long long &received, clock_t elapsed) {
  144. 		cerr << "Example " << casenum << "... ";
  145.  
  146. 		string verdict;
  147. 		vector<string> info;
  148. 		char buf[100];
  149.  
  150. 		if (elapsed > CLOCKS_PER_SEC / 200) {
  151. 			sprintf(buf, "time %.2fs", elapsed * (1.0/CLOCKS_PER_SEC));
  152. 			info.push_back(buf);
  153. 		}
  154.  
  155. 		if (expected == received) {
  156. 			verdict = "PASSED";
  157. 		} else {
  158. 			verdict = "FAILED";
  159. 		}
  160.  
  161. 		cerr << verdict;
  162. 		if (!info.empty()) {
  163. 			cerr << " (";
  164. 			for (int i=0; i<(int)info.size(); ++i) {
  165. 				if (i > 0) cerr << ", ";
  166. 				cerr << info[i];
  167. 			}
  168. 			cerr << ")";
  169. 		}
  170. 		cerr << endl;
  171.  
  172. 		if (verdict == "FAILED") {
  173. 			cerr << "    Expected: " << expected << endl;
  174. 			cerr << "    Received: " << received << endl;
  175. 		}
  176.  
  177. 		return verdict == "PASSED";
  178. 	}
  179.  
  180. 	int run_test_case(int casenum__) {
  181. 		switch (casenum__) {
  182. 		case 0: {
  183. 			int a[]                   = {1};
  184. 			int b[]                   = {2};
  185. 			long long expected__      = 4;
  186.  
  187. 			clock_t start__           = clock();
  188. 			long long received__      = CentaurCompanyDiv2().count(vector <int>(a, a + (sizeof a / sizeof a[0])), vector <int>(b, b + (sizeof b / sizeof b[0])));
  189. 			return verify_case(casenum__, expected__, received__, clock()-start__);
  190. 		}
  191. 		case 1: {
  192. 			int a[]                   = {2,2};
  193. 			int b[]                   = {1,3};
  194. 			long long expected__      = 7;
  195.  
  196. 			clock_t start__           = clock();
  197. 			long long received__      = CentaurCompanyDiv2().count(vector <int>(a, a + (sizeof a / sizeof a[0])), vector <int>(b, b + (sizeof b / sizeof b[0])));
  198. 			return verify_case(casenum__, expected__, received__, clock()-start__);
  199. 		}
  200. 		case 2: {
  201. 			int a[]                   = {1,2,3,4,5,6,7,8,9};
  202. 			int b[]                   = {2,3,4,5,6,7,8,9,10};
  203. 			long long expected__      = 56;
  204.  
  205. 			clock_t start__           = clock();
  206. 			long long received__      = CentaurCompanyDiv2().count(vector <int>(a, a + (sizeof a / sizeof a[0])), vector <int>(b, b + (sizeof b / sizeof b[0])));
  207. 			return verify_case(casenum__, expected__, received__, clock()-start__);
  208. 		}
  209. 		case 3: {
  210. 			int a[]                   = {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1};
  211. 			int b[]                   = {2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51};
  212. 			long long expected__      = 1125899906842675LL;
  213.  
  214. 			clock_t start__           = clock();
  215. 			long long received__      = CentaurCompanyDiv2().count(vector <int>(a, a + (sizeof a / sizeof a[0])), vector <int>(b, b + (sizeof b / sizeof b[0])));
  216. 			return verify_case(casenum__, expected__, received__, clock()-start__);
  217. 		}
  218. 		case 4: {
  219. 			int a[]                   = {10, 7, 2, 5, 6, 2, 4, 9, 7};
  220. 			int b[]                   = {8, 10, 10, 4, 1, 6, 2, 2, 3};
  221. 			long long expected__      = 144;
  222.  
  223. 			clock_t start__           = clock();
  224. 			long long received__      = CentaurCompanyDiv2().count(vector <int>(a, a + (sizeof a / sizeof a[0])), vector <int>(b, b + (sizeof b / sizeof b[0])));
  225. 			return verify_case(casenum__, expected__, received__, clock()-start__);
  226. 		}
  227.  
  228. 		// custom cases
  229.  
  230. /*      case 5: {
  231. 			int a[]                   = ;
  232. 			int b[]                   = ;
  233. 			long long expected__      = ;
  234.  
  235. 			clock_t start__           = clock();
  236. 			long long received__      = CentaurCompanyDiv2().count(vector <int>(a, a + (sizeof a / sizeof a[0])), vector <int>(b, b + (sizeof b / sizeof b[0])));
  237. 			return verify_case(casenum__, expected__, received__, clock()-start__);
  238. 		}*/
  239. /*      case 6: {
  240. 			int a[]                   = ;
  241. 			int b[]                   = ;
  242. 			long long expected__      = ;
  243.  
  244. 			clock_t start__           = clock();
  245. 			long long received__      = CentaurCompanyDiv2().count(vector <int>(a, a + (sizeof a / sizeof a[0])), vector <int>(b, b + (sizeof b / sizeof b[0])));
  246. 			return verify_case(casenum__, expected__, received__, clock()-start__);
  247. 		}*/
  248. /*      case 7: {
  249. 			int a[]                   = ;
  250. 			int b[]                   = ;
  251. 			long long expected__      = ;
  252.  
  253. 			clock_t start__           = clock();
  254. 			long long received__      = CentaurCompanyDiv2().count(vector <int>(a, a + (sizeof a / sizeof a[0])), vector <int>(b, b + (sizeof b / sizeof b[0])));
  255. 			return verify_case(casenum__, expected__, received__, clock()-start__);
  256. 		}*/
  257. 		default:
  258. 			return -1;
  259. 		}
  260. 	}
  261. }
  262.  
  263.  
  264. int main(int argc, char *argv[]) {
  265. 	if (argc == 1) {
  266. 		moj_harness::run_test();
  267. 	} else {
  268. 		for (int i=1; i<argc; ++i)
  269. 			moj_harness::run_test(atoi(argv[i]));
  270. 	}
  271. }
  272. // END CUT HERE
  273.  
  274.  
  275.  
Success #stdin #stdout 0s 3000KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/sV0aNY
language:
C++ (gcc 8.3)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!