Submission #1226117

#	Time	Username	Problem	Language	Result	Execution time	Memory
1226117		spetr	Homework (CEOI22_homework)	C++20	0 / 100	324 ms	589824 KiB

Main

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

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

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

void dfs(ll u){
if (v[u].list) {

    for (int x = 1; x <= n; x++)
        can[u][x] = true;
        return;
    }
    int L = v[u].L, R = v[u].R;
    dfs(L);
    dfs(R);

    if (v[u].typ == 0) {
                  
        for (int x = 1; x <= n; x++) {
            if ((can[L][x] && can[R][x+1]) || (can[R][x] && can[L][x+1]))
                can[u][x] = true;
            }
    } else {
            
        for (int x = 1; x <= n; x++) {
            if ((can[L][x] && can[R][x-1]) || (can[R][x] && can[L][x-1]))
                can[u][x] = true;
            }
    }
}


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

    string vstup;
    cin >> vstup;

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

    ll pos = 0;

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

    for (ll i = 4; i < (ll)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);
            ll 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);
            ll 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);

    int cnt = 0;
    for (int x = 1; x <= n; x++)
        if (can[0][x]) cnt++;
    cout << cnt - 1<< "\n";

    return 0;
}

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