Submission #1226170

#	Time	Username	Problem	Language	Result	Execution time	Memory
1226170		svtk	Homework (CEOI22_homework)	C++20	100 / 100	209 ms	132504 KiB

Main

#include <iostream>
#include <string>
using namespace std;

struct node{
    int l, r, n;
    bool min = false;
    bool max = false;
    bool num = false;
    int min_v, max_v;
    node* s1 = nullptr;
    node* s2 = nullptr;
};

string s;

node* read(int l){
    node* ans = new node;
    ans->l = l;
    if(s[l] == '?'){
        ans->num = true;
        ans->r = l+1;
        ans->n = 1;
    } else {
        ans->s1 = read(l+4);
        ans->s2 = read(ans->s1->r+1);
        ans->r = ans->s2->r+1;
        ans->n = ans->s1->n + ans->s2->n;
        if(s[l+1] == 'i'){
            ans->min = true;
        } else {
            ans->max = true;
        }
    }
    //cout << "My left is " << ans->l << ", my right is " << ans->r << " max: " << ans->max << endl;
    return ans;
}

void eval(node* root){
    if(root->num) {
        root->min_v = 0;
        root->max_v = 0;
        return;
    } else {
        eval(root->s1);
        eval(root->s2);
        if(root->min){
            root->min_v = min(root->s1->min_v, root->s2->min_v);
            root->max_v = root->s1->max_v + root->s2->max_v + 1;
        } else {
            root->min_v = root->s1->min_v + root->s2->min_v + 1;
            root->max_v = min(root->s1->max_v, root->s2->max_v);
        }
    }
}

int main(){
    cin >> s;
    node *root = read(0);
    eval(root);
    cout << root->n - root->min_v - root->max_v << endl;

    return 0;
}

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