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"
// @JASPER'S BOILERPLATE
using namespace std;
using ll = long long;
#ifdef JASPER
#include "debug.h"
#else
#define debug(...) 166
#endif
const int N = 1e6 + 5;
int n, sz;
string s;
vector <int> c;
struct Node {
int t;
Node *l, *r;
};
Node* make(int& i) {
Node* cur = new Node;
if (s[i] == '?') {
++i;
cur->t = 0;
cur->l = cur->r = nullptr;
return cur;
}
if (s[i + 1] == 'i') {
cur->t = -1;
}
else {
cur->t = -2;
}
i += 4;
cur->l = make(i);
++i;
cur->r = make(i);
++i;
return cur;
}
using T = array <int, 3>;
// cnt, up, lo;
T solve(Node* tr) {
if (tr->t == 0) return {1, 1, 1};
T ql = solve(tr->l);
T qr = solve(tr->r);
T res;
res[0] = ql[0] + qr[0];
if (tr->t == -1) {
res[1] = min(ql[1], qr[1]);
res[2] = ql[2] + qr[2] - 1;
}
else {
res[1] = ql[1] + qr[1];
res[2] = max(ql[2] + qr[0], qr[2] + ql[0]);
}
return res;
}
signed main() {
cin.tie(0) -> sync_with_stdio(0);
#ifdef JASPER
freopen("in1", "r", stdin);
#endif
cin >> s;
sz = s.size();
int p = 0;
Node* tr = make(p);
T ans = solve(tr);
debug(ans);
cout << (ans[2] - ans[1] + 1) << "\n";
// if (n >= 9) {
// c.resize(n);
// iota(c.begin(), c.end(), 1);
// vector <int> vals;
// do {
// vals.push_back(dfs(tr));
// } while (next_permutation(c.begin(), c.end()));
// sort(vals.begin(), vals.end());
// vals.resize(unique(vals.begin(), vals.end()) - vals.begin());
// cout << dfs(tr) << "\n";
// }
// else {
// debug(n);
// T ans = solve(tr);
// // debug(ans);
// // cout << (ans[2] - ans[1] + 1) << "\n";
// }
return 0;
}
Compilation message (stderr)
Main.cpp: In function 'int main()':
Main.cpp:9:20: warning: statement has no effect [-Wunused-value]
9 | #define debug(...) 166
| ^~~
Main.cpp:80:5: note: in expansion of macro 'debug'
80 | debug(ans);
| ^~~~~
# | 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... |