제출 #1369089

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1369089		fauntleroy	Homework (CEOI22_homework)	C++20	100 / 100	128 ms	146500 KiB

Main

#include <bits/stdc++.h>

using namespace std;

struct Node {
    int l = -1, r = -1;
    char op = '?'; 
};

string s;
int pos = 0;
vector<Node> tree;

int parse() {
    int id = tree.size();
    tree.push_back(Node());

    if (s[pos] == '?') {
        tree[id].op = '?';
        pos++;
        return id;
    }

    if (s[pos] == 'm' && s[pos + 1] == 'i') {
        tree[id].op = 'm'; 
        pos += 4; 
    }
    else {
        tree[id].op = 'M'; 
        pos += 4; 
    }

    tree[id].l = parse();

    pos++; 

    tree[id].r = parse();

    pos++; 

    return id;
}

struct tr {
    int L, R, sz;
};

tr dfs(int v) {
    if (tree[v].op == '?') {
        return {1, 1, 1};
    }

    tr a = dfs(tree[v].l);
    tr b = dfs(tree[v].r);

    tr res;
    res.sz = a.sz + b.sz;

    if (tree[v].op == 'm') {
        res.L = min(a.L, b.L);
        res.R = a.R + b.R - 1;
    }
    else {
        res.L = a.L + b.L;
        res.R = max(a.R + b.sz, b.R + a.sz);
    }

    return res;
}

void solve() { 
    cin >> s;

    pos = 0;
    tree.clear();

    int root = parse();
    tr ans = dfs(root);

    cout << ans.R - ans.L + 1 << '\n';
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    solve();

    return 0;    
}

• 서브태스크 1: 10 / 10
• 서브태스크 2: 13 / 13
• 서브태스크 3: 13 / 13
• 서브태스크 4: 30 / 30
• 서브태스크 5: 34 / 34