Submission #1126807

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126807		Pannda	Homework (CEOI22_homework)	C++20	100 / 100	332 ms	234292 KiB

Main

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

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

    string s;
    cin >> s;

    int num_nodes = 0;
    vector<int> type; // of size num_nodes, 0 for min, 1 for max, -1 for leaves
    vector<vector<int>> adj; // of size num_nodes

    auto build = [&](auto self, int &i0) -> int { // return the node id, point i0 to the end of the expression (exclusive)
        int u = num_nodes++;
        type.emplace_back();
        adj.emplace_back();
        if (s[i0] == '?') {
            type[u] = -1;
            i0++;
        } else {
            type[u] = s.substr(i0, 3) == "max" ? 1 : 0;
            i0 += 4; // skip max(
            int v0 = self(self, i0);
            i0++; // skip ,
            int v1 = self(self, i0);
            i0++; // skip )
            adj[u] = {v0, v1};
        }
        return u;
    };
    int goat = 0;
    int root = build(build, goat);

    auto dfs = [&](auto self, int u) -> pair<int, array<int, 2>> { // num leaves in subtree, force lower/upper
        if (type[u] == -1)  {
            return {1, {0, 0}};
        } else {
            auto A = self(self, adj[u][0]);
            auto B = self(self, adj[u][1]);
            if (type[u] == 0) {
                return {A.first + B.first, { min(A.second[0], B.second[0]), A.second[1] + B.second[1] + 1 }};
            } else {
                return {A.first + B.first, { A.second[0] + B.second[0] + 1, min(A.second[1], B.second[1]) }};
            }
        }
    };

    auto [num_leaves, lower_upper] = dfs(dfs, root);
    cout << num_leaves - lower_upper[0] - lower_upper[1] << '\n';
}

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