Submission #1218750

#	Time	Username	Problem	Language	Result	Execution time	Memory
1218750		toast12	Homework (CEOI22_homework)	C++20	100 / 100	395 ms	228896 KiB

Main

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

vector<int> type, l, r;
vector<vector<int>> adj;
vector<int> leaves;

void dfs(int cur, int p) {
    if (type[cur] == -1) {
        leaves[cur] = 1;
        return;
    }
    for (auto e : adj[cur]) {
        if (e != p) {
            dfs(e, cur);
            leaves[cur] += leaves[e];
        }
    }
    int lc = adj[cur][1];
    int rc = adj[cur][2];
    if (type[cur] == 1) {
        // max
        l[cur] = l[lc]+l[rc];
        r[cur] = max(r[lc]+leaves[rc], r[rc]+leaves[lc]);
    }
    else {
        // min
        l[cur] = min(l[lc], l[rc]);
        r[cur] = r[lc]+r[rc]-1;
    }
}

int main() {
    string s;
    getline(cin, s);
    int n = 0, q = 0;
    for (int i = 0; i < s.length(); i++) {
        if (s[i] == 'm') {
            n++;
            i += 3;
        }
        else if (s[i] == '?') {
            n++;
            i++;
            q++;
        }
    }
    adj.resize(2);
    type.resize(2, -1);
    l.resize(2);
    r.resize(2);
    int cur = 1;
    stack<int> st;
    st.push(1);
    adj[1].push_back(1);
    for (int i = 0; i < s.length(); i++) {
        if (s[i] != 'm' && s[i] != '?') continue;
        cur = st.top();
        st.pop();
        if (s[i] == 'm') {
            if (s[i+1] == 'a') type[cur] = 1;
            else type[cur] = 0;
            adj.emplace_back();
            adj[cur].push_back(adj.size()-1);
            adj[adj.size()-1].push_back(cur);
            adj.emplace_back();
            adj[cur].push_back(adj.size()-1);
            adj[adj.size()-1].push_back(cur);
            st.push(adj.size()-1);
            st.push(adj.size()-2);
            l.emplace_back();
            l.emplace_back();
            r.emplace_back();
            r.emplace_back();
            type.push_back(-1);
            type.push_back(-1);
            i += 3;
        }
        else if (s[i] == '?') {
            l[cur] = 1;
            r[cur] = 1;
        }
    }
    leaves.resize(adj.size());
    dfs(1, 1);
    cout << r[1]-l[1]+1 << '\n';
    return 0;
}

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