Submission #1004486

#TimeUsernameProblemLanguageResultExecution timeMemory
1004486ErJHomework (CEOI22_homework)C++17
100 / 100
105 ms101344 KiB
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define vi vector<ll>
#define pp pair<ll, ll>
#define vvi vector<vi>
#define inf 1000000000
#define rep(i,n) for(int i = 0; i < n; i++)

int pos;

pair<pp, int> createTree(string& s){ //max, min
    if(s[pos] == '?'){
        pos++;
        return {{1, 1}, 1};
    }
    pair<pp, int> ans;
    pair<pp, int> left ,right;
    if(s[pos + 1] =='a'){
        pos += 4;
        left = createTree(s);
        pos++;
        right = createTree(s);
        pos++;
        ans.second = left.second + right.second;
        ans.first.first = min(left.first.first, right.first.first);
        ans.first.second = left.first.second + right.first.second - 1;
    }else{
        pos += 4;
        left = createTree(s);
        pos++;
        right = createTree(s);
        pos++;
        ans.second = left.second + right.second;
        ans.first.first = left.first.first + right.first.first;
        ans.first.second = ans.second - min(left.second - left.first.second, right.second - right.first.second);
    }
    return ans;
};

int main(){
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    string s;
    cin >> s;
    pos = 0;
    pair<pp, int> x = createTree(s);
    pp ans = x.first;
    cout << ans.second - ans.first + 1 << endl;
}
#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...