fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int n;
  5. vector <int> e[1001];
  6. vector <int> nonTree_A;
  7. vector <int> nonTree_B;
  8. long long mod = 1000000007;
  9. bool mustTake[1001];
  10. bool mustNotTake[1001];
  11.  
  12. struct minimalAndWays
  13. {
  14. 	long long minimal;
  15. 	long long ways;
  16. 	minimalAndWays()
  17. 	{
  18. 		minimal = 1000000000;
  19. 		ways = 0;
  20. 	}
  21. 	minimalAndWays(long long _m, long long _w)
  22. 	{
  23. 		minimal = _m;
  24. 		ways = _w;
  25. 	}
  26. 	minimalAndWays add(const minimalAndWays &that) const
  27. 	{
  28. 		return minimalAndWays(minimal + that.minimal, (ways * that.ways) % mod);
  29. 	}
  30. 	minimalAndWays update(const minimalAndWays &that) const
  31. 	{
  32. 		if(minimal < that.minimal)
  33. 			return *this;
  34. 		if(minimal > that.minimal)
  35. 			return that;
  36. 		return minimalAndWays(minimal, (ways + that.ways) % mod);
  37. 	}
  38. }inf, zero(0, 1);
  39.  
  40. long long calls = 0;
  41. bool done[1001][2];
  42. minimalAndWays mem[1001][2];
  43.  
  44. minimalAndWays dp(int cur, int from, int takeThis)
  45. {
  46. 	calls ++;
  47. 	if(mustTake[cur] && !takeThis) return inf;
  48. 	if(mustNotTake[cur] && takeThis) return inf;
  49. 	if(done[cur][takeThis]) return mem[cur][takeThis];
  50. 	minimalAndWays ret = zero;
  51. 	for(int i = 0; i < e[cur].size(); i++)
  52. 	{
  53. 		int t = e[cur][i];
  54. 		if(t == from) continue;
  55. 		minimalAndWays w = dp(t, cur, 1);
  56. 		if(takeThis)
  57. 			w = w.update(dp(t, cur, 0));
  58. 		ret = ret.add(w);
  59. 	}
  60. 	if(takeThis)
  61. 		ret.minimal += 1;
  62. 	done[cur][takeThis] = true;
  63. 	mem[cur][takeThis] = ret;
  64. 	return ret;
  65. }
  66.  
  67. class VampireTreeDiv2
  68. {
  69. 	public:	int countMinSamples(vector <int> A, vector <int> B)
  70. 	{
  71. 		n = A.size() + 1;
  72. 		for(int i = 1; i < n; i++)
  73. 		{
  74. 			e[i].push_back(A[i-1]);
  75. 			e[A[i-1]].push_back(i);
  76. 			if(B[i-1] != -1)
  77. 			{
  78. 				nonTree_A.push_back(i);
  79. 				nonTree_B.push_back(B[i-1]);
  80. 			}
  81. 		}
  82. 		minimalAndWays ret;
  83. 		for(int mask = 0; mask < (1<<(nonTree_A.size())); mask ++)
  84. 		{
  85. 			memset(mustTake, false, sizeof(mustTake));
  86. 			memset(mustNotTake, false, sizeof(mustNotTake));
  87. 			memset(done, false, sizeof(done));
  88. 			for(int i = 0; i < nonTree_A.size(); i++)
  89. 				if((mask & (1<<i)) > 0)
  90. 					mustTake[nonTree_A[i]] = true;
  91. 				else
  92. 				{
  93. 					mustTake[nonTree_B[i]] = true;
  94. 					mustNotTake[nonTree_A[i]] = true;
  95. 				}
  96. 			ret = ret.update(dp(0, -1, 0));
  97. 			ret = ret.update(dp(0, -1, 1));
  98. 		}
  99. 		return ret.ways;
  100. 	}
  101. };
  102.  
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
/usr/lib/gcc/i586-linux-gnu/5/../../../i386-linux-gnu/crt1.o: In function `_start':
(.text+0x18): undefined reference to `main'
collect2: error: ld returned 1 exit status
stdout
copy 
Standard output is empty
https://ideone.com/fv4IXx
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
secret

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!