fork download
  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
stdin
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
Standard output is empty