oj.uz

Submission #725818

# Submission time Handle Problem Language Result Execution time Memory
725818 2023-04-18T06:32:33 Z tengiz05 Homework (CEOI22_homework) C++17
0 / 100
 302 ms 524292 KB 
#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] == '?') 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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 269 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 269 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 302 ms 524292 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 269 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 34.0

# Verdict Execution time Memory Grader output
1 Runtime error 269 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -