# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
861218 | vgtcross | Homework (CEOI22_homework) | C++17 | 96 ms | 128208 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int N = int(1e6) + 1000;
vector<int> ch[N];
int l[N], r[N];
int x[N];
void dfs(int u) {
if (x[u] == 0) {
l[u] = r[u] = 0;
return;
}
for (int v : ch[u]) dfs(v);
if (x[u] == 1) {
l[u] = min(l[ch[u][0]], l[ch[u][1]]);
r[u] = r[ch[u][0]] + r[ch[u][1]] + 1;
} else {
l[u] = l[ch[u][0]] + l[ch[u][1]] + 1;
r[u] = min(r[ch[u][0]], r[ch[u][1]]);
}
}
void solve() {
string s;
cin >> s;
stack<int> st;
st.push(0);
int w = 1;
int i = 0;
while (i < s.size()) {
if (s[i] == '?') ch[st.top()].push_back(w++);
else if (s[i] == 'm') {
x[w] = s[i+1] == 'a' ? 2 : 1;
ch[st.top()].push_back(w);
st.push(w++);
i += 3;
} else if (s[i] == ')') st.pop();
++i;
}
dfs(1);
int cnt = 0;
for (char c : s) cnt += c == '?';
cout << cnt - l[1] - r[1] << '\n';
}
int main() {
cin.tie(0) -> sync_with_stdio(0);
solve();
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |