Submission #725820

#	Time	Username	Problem	Language	Result	Execution time	Memory
725820		tengiz05	Homework (CEOI22_homework)	C++17	100 / 100	143 ms	112220 KiB

Main

#include <bits/stdc++.h>

using i64 = long long;

constexpr int N = 2E6 + 5;
std::string s;
int n;
int type[N];
std::array<int, 2> e[N];
int nd = 0;
int dfs(int u, int l) {
    if (s[l] == '?') {
        type[u] = -1;
        return l + 1;
    }
    ++nd;
    if (s.substr(l, 3) == "min") {
        type[u] = 0;
    } else if (s.substr(l, 3) == "max") {
        type[u] = 1;
    } else assert(false);
    e[u][0] = nd;
    l = dfs(nd, l + 4) + 1;
    ++nd;
    e[u][1] = nd;
    l = dfs(nd, l) + 1;
    return l;
}
int zero[N], one[N];
void fill(int u) {
    if (type[u] == -1) {
        zero[u] = one[u] = 1;
        return;
    }
    fill(e[u][0]);
    fill(e[u][1]);
    if (type[u] == 0) {
        zero[u] = std::min(zero[e[u][0]], zero[e[u][1]]);
        one[u] = one[e[u][0]] + one[e[u][1]];
    } else {
        zero[u] = zero[e[u][0]] + zero[e[u][1]];
        one[u] = std::min(one[e[u][0]], one[e[u][1]]);
    }
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    std::cin >> s;
    
    n = std::count(s.begin(), s.end(), '?');
    
    dfs(0, 0);
    fill(0);
    
    int Min = zero[0];
    int Max = n - one[0] + 1;
    
    std::cout << Max - Min + 1 << "\n";
    
    return 0;
}

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