fork download

copy

class ParenthesesDiv1Hard {
 public:
  template <class It>
  void parse(It b, It e, int root, vi* parent) {
    if (b == e) {
      return;
    }
    int sum = 1;
    ++b;
    int v = parent->size();
    parent->push_back(root);
    It s = b;
    while (sum) {
      if (*b == '(') {
        ++sum;
      } else {
        --sum;
      }
      ++b;
    }
    parse(b, e, root, parent);
    parse(s, prev(b), v, parent);
  }
 
  map<int, int> depth;
 
  int dfs(int r, const vii& al) {
    depth[r] = 1;
    for (int v2 : al[r]) {
      depth[r] = max(depth[r], 1 + dfs(v2, al));
    }
    return depth[r];
  }
 
  int cost(int r, const vii& al) {
    int res = 0;
    res += depth[r] * depth[r];
    for (int v2 : al[r]) {
      res += cost(v2, al);
    }
    return res;
  }
 
  int minCost(string s) {
    int sum = 0;
    for (int i = 0; i < s.size(); ++i) {
      if (s[i] == '(') {
        ++sum;
      } else {
        --sum;
      }
      if (sum < 0) {
        return -1;
      }
    }
    if (sum) {
      return -1;
    }
    vi parent;
    parse(s.begin(), s.end(), -1, &parent);
 
    vii al(parent.size());
    vi roots;
    for (size_t v = 0; v < parent.size(); ++v) {
      int p = parent[v];
      if (p == -1) {
        roots.push_back(v);
        continue;
      }
      p = parent[p];
      if (p == -1) {
        roots.push_back(v);
        continue;
      }
      al[p].push_back(v);
    }
 
    for (int r : roots) {
      dfs(r, al);
    }
 
    int res = 0;
    for (int r : roots) {
      res += cost(r, al);
    }
 
    return res;
  }
};
 

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);
                      ^

Standard output is empty