Submission #639526

#	Time	Username	Problem	Language	Result	Execution time	Memory
639526		MilosMilutinovic	Homework (CEOI22_homework)	C++14	100 / 100	299 ms	233120 KiB

Main

/**
 *    author:  wxhtzdy
 *    created: 07.09.2022 19:09:46
**/
#include <bits/stdc++.h>

using namespace std;

string to_string(string s) {
  return '"' + s + '"';
}
string to_string(const char* s) {
  return to_string((string) s);
}
string to_string(bool b) {
  return (b ? "true" : "false");
}
template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
template <typename A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto &x : v) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);  
  string s;
  cin >> s;
  int len = (int) s.size();
  vector<int> stk;
  vector<int> mat(len);
  for (int i = 0; i < len; i++) {
    if (s[i] == '(') {
      stk.push_back(i); 
    }
    if (s[i] == ')') {
      mat[stk.back()] = i;
      stk.pop_back();
    }
  }     
  int n = 0;
  for (int i = 0; i < len; i++) {
    if (s[i] == '?') {
      n += 1;
    }
  }
  vector<vector<int>> g(2 * n);
  vector<int> type(2 * n);
  int T = 0;
  function<void(int, int, int)> Solve = [&](int L, int R, int idx) {
    if (L == R) {
      return;
    }
    if (s[L + 1] == 'i') {
      type[idx] = 0;
    } else {
      type[idx] = 1;
    }
    T++;
    g[idx].push_back(T);
    L = L + 4;  
    if (s[L] != '?') {
      Solve(L, mat[L + 3], T);
      L = mat[L + 3] + 2;
    } else {
      L += 2;
    }
    T++;
    g[idx].push_back(T);
    if (s[L] != '?') {
      Solve(L, R - 1, T);  
    }
  };
  Solve(0, len - 1, 0);
  vector<int> L(2 * n);
  vector<int> R(2 * n);
  vector<int> sz(2 * n);
  function<void(int)> Dfs = [&](int v) {
    if (g[v].empty()) {
      L[v] = R[v] = sz[v] = 1;
      return;
    }
    assert((int) g[v].size() == 2);
    for (int u : g[v]) {
      Dfs(u);        
    }           
    sz[v] = sz[g[v][0]] + sz[g[v][1]];
    if (type[v] == 0) {
      L[v] = min(L[g[v][0]], L[g[v][1]]);    
      R[v] = R[g[v][0]] + R[g[v][1]] - 1;
    } else {
      L[v] = L[g[v][0]] + L[g[v][1]];
      R[v] = max(R[g[v][0]] + sz[g[v][1]], sz[g[v][0]] + R[g[v][1]]);
    }
  };
  Dfs(0);
  cout << R[0] - L[0] + 1 << '\n';                                               
  return 0;
}                                    

• Subtask 1: 10 / 10
• Subtask 2: 13 / 13
• Subtask 3: 13 / 13
• Subtask 4: 30 / 30
• Subtask 5: 34 / 34