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 i64 = long long;
#ifdef DEBUG
#include "debug.h"
#else
#define debug(...) void(23)
#endif
constexpr int max_N = int(2E6) + 5;
int N;
std::vector<int> adj[max_N];
int tp[max_N], siz[max_N];
std::pair<int, int> dfs(int v) {
debug(v, tp[v], adj[v]);
if (tp[v] == 0) {
return {0, 0};
}
int u0 = adj[v][0];
int u1 = adj[v][1];
auto r0 = dfs(u0);
auto r1 = dfs(u1);
siz[v] = siz[u0] + siz[u1];
std::pair<int, int> res;
if (tp[v] == -1) {
res = {std::min(r0.first, r1.first), r0.second + r1.second};
} else {
res = {r0.first + r1.first + 1, std::max(r0.second + siz[u1], r1.second + siz[u0])};
}
debug(v, res);
return res;
}
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
std::string S;
std::cin >> S;
int nv = 0;
std::vector<int> stk;
for (int i = 0; i < S.size(); ++i) {
if (S[i] == '(') {
tp[nv] = (S[i - 1] == 'n' ? -1 : +1);
if (!stk.empty()) {
adj[stk.back()].emplace_back(nv);
}
stk.emplace_back(nv++);
} else if (S[i] == '?') {
tp[nv] = 0;
siz[nv] = 1;
adj[stk.back()].emplace_back(nv++);
} else if (S[i] == ')') {
stk.pop_back();
}
}
N = nv;
auto x = dfs(0);
std::cout << x.second - x.first + 1 << '\n';
return 0;
}
Compilation message (stderr)
Main.cpp: In function 'int main()':
Main.cpp:46:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
46 | for (int i = 0; i < S.size(); ++i) {
| ~~^~~~~~~~~~
# | 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... |