Advertisement
Guest User

Untitled

a guest
May 14th, 2017
79
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.07 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <assert.h>
  3. #include <vector>
  4. #include <iostream>
  5. #define MAXN 1000000
  6.  
  7. int maxResult = 0;
  8. using namespace std;
  9. vector<int> arr;
  10.  
  11. void calculateAt(int i, const int MAXf, const char Q[], const int A[])
  12. {
  13.  
  14. if(i >= MAXf)
  15. return;
  16. else
  17. {
  18. if(arr[i] == -1)
  19. {
  20.  
  21. if(arr[A[i]] == -1)
  22. calculateAt(A[i], MAXf, Q, A);
  23.  
  24. arr[i] = arr[A[i]] + (Q[i] == 'P' ? 1 : (Q[i] == 'N' ? 2 : 3));
  25.  
  26. if(arr[i] > maxResult)
  27. maxResult = arr[i];
  28.  
  29. }
  30. calculateAt(i+1, MAXf, Q, A);
  31. }
  32. }
  33.  
  34. int falsifica(int N, char Q[], int A[]) {
  35. // Mettete qui il codice della soluzione
  36.  
  37. // calculateAt(1, N, Q, A);
  38.  
  39. vector<int> coda;
  40.  
  41. int i = 1;
  42.  
  43. coda.push_back(0);
  44.  
  45. while(i < N)
  46. {
  47. if(arr[i] == -1)
  48. {
  49.  
  50. if(arr[A[i]] == -1)
  51. {
  52. i = A[i];
  53. coda.push_back(i);
  54. continue;
  55. }
  56. // calculateAt(A[i], MAXf, Q, A);
  57.  
  58. arr[i] = arr[A[i]] + (Q[i] == 'P' ? 1 : (Q[i] == 'N' ? 2 : 3));
  59.  
  60. if(arr[i] > maxResult)
  61. maxResult = arr[i];
  62.  
  63. }
  64.  
  65. // if(coda.size() > 0)
  66. // coda.erase(coda.size()-1);
  67. if(coda.size() > 1)
  68. {
  69. coda.erase(coda.begin() + coda.size()-1);
  70. i = coda[coda.size()-1] -1;
  71.  
  72. }
  73.  
  74. if(coda.size() == 1)
  75. {
  76. i++;
  77. coda[0] = i;
  78. }
  79. }
  80.  
  81.  
  82. return maxResult;
  83. }
  84.  
  85.  
  86. char Q[MAXN];
  87. int A[MAXN];
  88.  
  89. int main() {
  90. int N, i;
  91.  
  92. freopen("input.txt", "r", stdin);
  93. freopen("output.txt", "w", stdout);
  94. cin >> N;
  95. Q[0] = 'X';
  96. A[0] = -1;
  97. arr.push_back(0);
  98. for(i=1; i<N; i++) {
  99. cin >> Q[i];
  100. cin >> A[i];
  101. // assert(1 == fscanf(fr, " %c", &Q[i]));
  102. // assert(1 == fscanf(fr, "%d", &A[i]));
  103. arr.push_back(-1);
  104. }
  105.  
  106. cout << falsifica(N, Q, A);
  107.  
  108. return 0;
  109. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement