Submission #735868

#	Time	Username	Problem	Language	Result	Execution time	Memory
735868		tch1cherin	Homework (CEOI22_homework)	C++17	100 / 100	470 ms	202296 KiB

Main

#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> g;
vector<int> t, S, Min, Max;

void DFS(int u) {
  if (t[u] == 3) {
    Min[u] = Max[u] = S[u] = 1;
    return;
  }
  for (int v : g[u]) {
    DFS(v);
    S[u] += S[v];
    if (t[u] == 1) {
      Max[u] += S[v] - Max[v] + 1; 
    } else {
      Min[u] += Min[v];
    }
  }
  if (t[u] == 1) {
    Min[u] = S[u];
    for (int v : g[u]) {
      Min[u] = min(Min[u], Min[v]);
    }
    Max[u] = S[u] - Max[u] + 1; 
  } else { 
    Max[u] = 1;
    for (int v : g[u]) {
      Max[u] = max(Max[u], S[u] - (S[v] - Max[v]));
    }
  }
}

int main() {
  string s;
  cin >> s;
  int N = (int)s.size();
  stack<int> st;
  for (int i = 0; i < N; i++) {
    if (i + 2 < N && s[i] == 'm' && s[i + 1] == 'i' && s[i + 2] == 'n') {
      st.push((int)g.size());
      g.push_back({});
      t.push_back(1);
    } else if (i + 2 < N && s[i] == 'm' && s[i + 1] == 'a' && s[i + 2] == 'x') {
      st.push((int)g.size());
      g.push_back({});
      t.push_back(2);
    } else if (s[i] == '?') {
      g[st.top()].push_back((int)g.size());
      g.push_back({});
      t.push_back(3);
    } else if (s[i] == ')') {
      int x = st.top();
      st.pop();
      if (!st.empty()) {
        g[st.top()].push_back(x);
      }
    }
  }
  S = Min = Max = vector<int>(g.size());
  DFS(0);
  cout << Max[0] - Min[0] + 1 << "\n";
}

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