제출 #1226158

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1226158		spetr	Homework (CEOI22_homework)	C++20	53 / 100	354 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;
    ll pocet;
    bool list;
    ll maximum, minimum;
    ll L = -1, R = -1;
    Node(ll t, ll sz, ll r, ll b)
      : typ(t), rodic(r), list(b), pocet(0), minimum(0), maximum(0) {}
};
vector<Node> v;
vector<vb> can;

void dfs(ll 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(ll u){
    if (v[u].list){
        v[u].minimum = v[u].maximum = 1;
        return;
    }
    dfs2(v[u].L);
    dfs2(v[u].R);
    ll 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;
    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);
    dfs2(0);

    ll 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