Submission #734687

#	Time	Username	Problem	Language	Result	Execution time	Memory
734687		tch1cherin	Homework (CEOI22_homework)	C++17	13 / 100	595 ms	319684 KiB

Main

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

vector<vector<int>> g;
vector<int> t, l, r;
int n = 0;

void DFS(int u) {
  l[u] = n, r[u] = 1;
  vector<int> same, adj;
  for (int v : g[u]) {
    if (t[v] == t[u]) {
      same.push_back(v);
    } else {
      adj.push_back(v);
    }
  }
  while (!same.empty()) {
    int x = same.back();
    same.pop_back();
    for (int v : g[x]) {
      if (t[v] == t[u]) {
        same.push_back(v);
      } else {
        adj.push_back(v);
      }
    }
  }
  g[u] = adj;
  for (int v : g[u]) {
    DFS(v);
    l[u] = min(l[u], l[v]);
    r[u] = max(r[u], r[v]);
  }
  if (t[u] == 1) {
    r[u] -= g[u].size() - 1;  
  } else if (t[u] == 2) {
    l[u] += g[u].size() - 1;
  } else {
    l[u] = 1, r[u] = n; 
  }
}

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

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