oj.uz

Submission #734687

# Submission time Handle Problem Language Result Execution time Memory
734687 2023-05-02T20:11:11 Z tch1cherin Homework (CEOI22_homework) C++17
13 / 100
 595 ms 319684 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Correct 1 ms 296 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Incorrect 1 ms 212 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Correct 1 ms 296 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Incorrect 1 ms 212 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 418 ms 119240 KB Output is correct
2 Correct 362 ms 123956 KB Output is correct
3 Correct 542 ms 227040 KB Output is correct
4 Correct 545 ms 227128 KB Output is correct
5 Correct 449 ms 161908 KB Output is correct
6 Correct 460 ms 161804 KB Output is correct
7 Correct 456 ms 161744 KB Output is correct
8 Correct 459 ms 161756 KB Output is correct
9 Correct 576 ms 319684 KB Output is correct
10 Correct 595 ms 319512 KB Output is correct
11 Correct 567 ms 319540 KB Output is correct
12 Correct 564 ms 319616 KB Output is correct
13 Correct 1 ms 212 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Correct 1 ms 296 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Incorrect 1 ms 212 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Correct 1 ms 296 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Incorrect 1 ms 212 KB Output isn't correct
5 Halted 0 ms 0 KB -