Submission #1226161

#	Time	Username	Problem	Language	Result	Execution time	Memory
1226161		spetr	Homework (CEOI22_homework)	C++20	53 / 100	344 ms	589824 KiB

Main

#include <bits/stdc++.h>
using namespace std;

const int mmod = 998244353;  
#define vb vector<bool>

int n = 0;
struct Node {
    int typ;    // 0 = min, 1 = max
    int rodic;
    int pocet;
    bool list;
    int maximum, minimum;
    int L = -1, R = -1;
    Node(int t, int sz, int r, int b)
      : typ(t), rodic(r), list(b), pocet(0), minimum(0), maximum(0) {}
};
vector<Node> v;
vector<vb> can;

void dfs(int u){
    if (v[u].list){
        v[u].pocet = 1;
    }
    else{
        dfs(v[u].L);
        dfs(v[u].R);
        v[u].pocet = v[v[u].L].pocet + v[v[u].R].pocet;
    }
}

void dfs2(int u){
    if (v[u].list){
        v[u].minimum = v[u].maximum = 1;
        return;
    }
    dfs2(v[u].L);
    dfs2(v[u].R);
    int l = v[u].L, r = v[u].R;
       

    if (v[u].typ == 0){
        v[u].minimum = min(v[l].minimum, v[r].minimum);
        v[u].maximum = v[l].maximum + v[r].maximum-1;
    }
    else{
        v[u].maximum = max(v[l].maximum + v[r].pocet, v[r].maximum + v[l].pocet);
        v[u].minimum = v[l].minimum + v[r].minimum;
    }
    
}


int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string vstup;
    getline(cin, vstup);

    n = 0;
    for(char c : vstup)
        if (c == '?') n++;

    int pos = 0;

    if (vstup[1] == 'i')       // "min"
        v.emplace_back(0, n, -1, false);
    else                       // "max"
        v.emplace_back(1, n, -1, false);

    for (int i = 4; i < (int)vstup.size(); i++){
        char c = vstup[i];
        if (c == '(') continue;
        if (c == 'm') {
            if (vstup[i+1] == 'i')
                v.emplace_back(0, n, pos, false);
            else
                v.emplace_back(1, n, pos, false);
            int u = v.size() - 1;
            if (v[pos].L == -1) v[pos].L = u; else v[pos].R = u;
            pos = u;
        }
        else if (c == ')' || c == ',') {
            pos = v[pos].rodic;
        }
        else if (c == '?') {
            v.emplace_back(0, n, pos, true);
            int u = v.size() - 1;
            if (v[pos].L == -1) v[pos].L = u; else v[pos].R = u;
            pos = u;
        }
    }



    //--------------------------------------------------------
    int M = v.size();

    can.resize(M, vb(n+1,false));


    dfs(0);
    dfs2(0);

    int cnt = v[0].maximum - v[0].minimum + 1;
    cout << cnt;
    

    return 0;
}

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