fork download
  1. class ParenthesesDiv1Hard {
  2. public:
  3. template <class It>
  4. void parse(It b, It e, int root, vi* parent) {
  5. if (b == e) {
  6. return;
  7. }
  8. int sum = 1;
  9. ++b;
  10. int v = parent->size();
  11. parent->push_back(root);
  12. It s = b;
  13. while (sum) {
  14. if (*b == '(') {
  15. ++sum;
  16. } else {
  17. --sum;
  18. }
  19. ++b;
  20. }
  21. parse(b, e, root, parent);
  22. parse(s, prev(b), v, parent);
  23. }
  24.  
  25. map<int, int> depth;
  26.  
  27. int dfs(int r, const vii& al) {
  28. depth[r] = 1;
  29. for (int v2 : al[r]) {
  30. depth[r] = max(depth[r], 1 + dfs(v2, al));
  31. }
  32. return depth[r];
  33. }
  34.  
  35. int cost(int r, const vii& al) {
  36. int res = 0;
  37. res += depth[r] * depth[r];
  38. for (int v2 : al[r]) {
  39. res += cost(v2, al);
  40. }
  41. return res;
  42. }
  43.  
  44. int minCost(string s) {
  45. int sum = 0;
  46. for (int i = 0; i < s.size(); ++i) {
  47. if (s[i] == '(') {
  48. ++sum;
  49. } else {
  50. --sum;
  51. }
  52. if (sum < 0) {
  53. return -1;
  54. }
  55. }
  56. if (sum) {
  57. return -1;
  58. }
  59. vi parent;
  60. parse(s.begin(), s.end(), -1, &parent);
  61.  
  62. vii al(parent.size());
  63. vi roots;
  64. for (size_t v = 0; v < parent.size(); ++v) {
  65. int p = parent[v];
  66. if (p == -1) {
  67. roots.push_back(v);
  68. continue;
  69. }
  70. p = parent[p];
  71. if (p == -1) {
  72. roots.push_back(v);
  73. continue;
  74. }
  75. al[p].push_back(v);
  76. }
  77.  
  78. for (int r : roots) {
  79. dfs(r, al);
  80. }
  81.  
  82. int res = 0;
  83. for (int r : roots) {
  84. res += cost(r, al);
  85. }
  86.  
  87. return res;
  88. }
  89. };
  90.  
Compilation error #stdin compilation error #stdout 0s 0KB
stdin
Standard input is empty
compilation info
prog.cpp:4:36: error: 'vi' has not been declared
   void parse(It b, It e, int root, vi* parent) {
                                    ^
prog.cpp:25:3: error: 'map' does not name a type
   map<int, int> depth;
   ^
prog.cpp:27:24: error: 'vii' does not name a type
   int dfs(int r, const vii& al) {
                        ^
prog.cpp:35:25: error: 'vii' does not name a type
   int cost(int r, const vii& al) {
                         ^
prog.cpp:44:15: error: 'string' has not been declared
   int minCost(string s) {
               ^
prog.cpp: In member function 'void ParenthesesDiv1Hard::parse(It, It, int, int*)':
prog.cpp:10:21: error: request for member 'size' in 'parent->', which is of non-class type 'int'
     int v = parent->size();
                     ^
prog.cpp:11:13: error: request for member 'push_back' in 'parent->', which is of non-class type 'int'
     parent->push_back(root);
             ^
prog.cpp: In member function 'int ParenthesesDiv1Hard::dfs(int, const int&)':
prog.cpp:28:5: error: 'depth' was not declared in this scope
     depth[r] = 1;
     ^
prog.cpp:29:23: error: invalid types 'const int[int]' for array subscript
     for (int v2 : al[r]) {
                       ^
prog.cpp:30:47: error: 'max' was not declared in this scope
       depth[r] = max(depth[r], 1 + dfs(v2, al));
                                               ^
prog.cpp: In member function 'int ParenthesesDiv1Hard::cost(int, const int&)':
prog.cpp:37:12: error: 'depth' was not declared in this scope
     res += depth[r] * depth[r];
            ^
prog.cpp:38:23: error: invalid types 'const int[int]' for array subscript
     for (int v2 : al[r]) {
                       ^
prog.cpp: In member function 'int ParenthesesDiv1Hard::minCost(int)':
prog.cpp:46:27: error: request for member 'size' in 's', which is of non-class type 'int'
     for (int i = 0; i < s.size(); ++i) {
                           ^
prog.cpp:47:14: error: invalid types 'int[int]' for array subscript
       if (s[i] == '(') {
              ^
prog.cpp:59:5: error: 'vi' was not declared in this scope
     vi parent;
     ^
prog.cpp:60:13: error: request for member 'begin' in 's', which is of non-class type 'int'
     parse(s.begin(), s.end(), -1, &parent);
             ^
prog.cpp:60:24: error: request for member 'end' in 's', which is of non-class type 'int'
     parse(s.begin(), s.end(), -1, &parent);
                        ^
prog.cpp:60:36: error: 'parent' was not declared in this scope
     parse(s.begin(), s.end(), -1, &parent);
                                    ^
prog.cpp:62:5: error: 'vii' was not declared in this scope
     vii al(parent.size());
     ^
prog.cpp:63:8: error: expected ';' before 'roots'
     vi roots;
        ^
prog.cpp:64:10: error: 'size_t' was not declared in this scope
     for (size_t v = 0; v < parent.size(); ++v) {
          ^
prog.cpp:64:24: error: 'v' was not declared in this scope
     for (size_t v = 0; v < parent.size(); ++v) {
                        ^
prog.cpp:67:9: error: 'roots' was not declared in this scope
         roots.push_back(v);
         ^
prog.cpp:72:9: error: 'roots' was not declared in this scope
         roots.push_back(v);
         ^
prog.cpp:75:7: error: 'al' was not declared in this scope
       al[p].push_back(v);
       ^
prog.cpp:78:18: error: 'roots' was not declared in this scope
     for (int r : roots) {
                  ^
prog.cpp:79:14: error: 'al' was not declared in this scope
       dfs(r, al);
              ^
prog.cpp:83:18: error: 'roots' was not declared in this scope
     for (int r : roots) {
                  ^
prog.cpp:84:22: error: 'al' was not declared in this scope
       res += cost(r, al);
                      ^
stdout
Standard output is empty