Submission #1350314

#TimeUsernameProblemLanguageResultExecution timeMemory
1350314ericl23302Homework (CEOI22_homework)C++20
100 / 100
120 ms144664 KiB
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    string str;
    cin >> str;
    if (str == "?") {
        cout << "1\n";
        return 0;
    }
    vector<pair<int, int>> nodes;
    vector<int> stk, type;
    int sz = str.size();
    for (int i = 0; i < sz; ++i) {
        if (str[i] == 'n') {
            if (!stk.empty()) {
                if (nodes[stk.back()].first == -2)
                    nodes[stk.back()].first = nodes.size();
                else
                    nodes[stk.back()].second = nodes.size();
            }
            stk.push_back(nodes.size());
            type.push_back(0);
            nodes.emplace_back(-2, -2);
        } else if (str[i] == 'x') {
            if (!stk.empty()) {
                if (nodes[stk.back()].first == -2)
                    nodes[stk.back()].first = nodes.size();
                else
                    nodes[stk.back()].second = nodes.size();
            }
            stk.push_back(nodes.size());
            type.push_back(1);
            nodes.emplace_back(-2, -2);
        } else if (str[i] == '?') {
            if (nodes[stk.back()].first == -2)
                nodes[stk.back()].first = -1;
            else
                nodes[stk.back()].second = -1;
        } else if (str[i] == ')')
            stk.pop_back();
    }

    int n = nodes.size();
    vector<int> l(n), r(n), s(n);

    auto recurse = [&](int cur, auto recurse) -> void {
        int l1 = 1, r1 = 1, s1 = 1, l2 = 1, r2 = 1, s2 = 1;
        if (nodes[cur].first != -1) {
            recurse(nodes[cur].first, recurse);
            l1 = l[nodes[cur].first];
            r1 = r[nodes[cur].first];
            s1 = s[nodes[cur].first];
        }
        if (nodes[cur].second != -1) {
            recurse(nodes[cur].second, recurse);
            l2 = l[nodes[cur].second];
            r2 = r[nodes[cur].second];
            s2 = s[nodes[cur].second];
        }
        if (type[cur]) {
            l[cur] = l1 + l2;
            r[cur] = max(r1 + s2, r2 + s1);
        } else {
            l[cur] = min(l1, l2);
            r[cur] = r1 + r2 - 1;
        }
        s[cur] = s1 + s2;
    };

    recurse(0, recurse);
    cout << (r[0] - l[0] + 1) << '\n';

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...