Submission #1004486

#	Time	Username	Problem	Language	Result	Execution time	Memory
1004486		ErJ	Homework (CEOI22_homework)	C++17	100 / 100	105 ms	101344 KiB

Main

#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;
}

• Subtask 1: 10 / 10
• Subtask 2: 13 / 13
• Subtask 3: 13 / 13
• Subtask 4: 30 / 30
• Subtask 5: 34 / 34