Submission #1161908

#	Time	Username	Problem	Language	Result	Execution time	Memory
1161908		antonn	Homework (CEOI22_homework)	C++20	53 / 100	285 ms	300876 KiB

Main

#include <bits/stdc++.h>

#define F first
#define S second
 
using namespace std;
using ll = long long;
using pi = pair<int, int>;
using vi = vector<int>;
 
template<class T> bool ckmin(T& a, T b) { return b < a ? a = b, true : false; }
template<class T> bool ckmax(T& a, T b) { return a < b ? a = b, true : false; }

const int N = 1e6 + 7;

string s; 
vector<int> g[4 * N];
int id[N], other[N], type[4 * N]; 
int nodes = 0;

int make_tree(int l, int r) {
    vector<int> sons;
    int nxt = 0;
    if (s[l+4] == '?') {
        sons.push_back(id[l+4]);
        nxt = l+6;
    } else {
        sons.push_back(make_tree(l+4, other[l+7]));
        nxt = other[l+7]+2;
    }
        
    if (s[nxt] == '?') {
        sons.push_back(id[nxt]);
    } else {
        sons.push_back(make_tree(nxt, other[nxt+3]));
    }
    ++nodes;
    for (auto x : sons) g[nodes].push_back(x);
    
    if (s[l] == 'm' && s[l+1] == 'i' && s[l+2] == 'n') type[nodes] = 0;
    if (s[l] == 'm' && s[l+1] == 'a' && s[l+2] == 'x') type[nodes] = 1;
    return nodes;
}

struct S {
    int l;
    int r;
    int leaves;
};

S join(S a, S b, bool type) {
    S c;
    if (type == 1) {
        c.l = a.l + b.l;
        c.r = max(a.r + b.leaves, b.r + a.leaves);
    } else {
        c.l = min(a.l, b.l);
        c.r = a.r + b.r - 1;
    }
    c.leaves = a.leaves + b.leaves;
    return c;
}

S dfs(int u) {
    if (g[u].size() == 0) return {1, 1, 1};
    
    S x = dfs(g[u][0]), y = dfs(g[u][1]);
    return join(x, y, type[u]);
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    
    cin >> s;
    if (s == "?") {
        cout << 1 << "\n";
        return 0;
    }
    
    int n = s.size();
    s = "#" + s;
    
    for (int i = 1; i <= n; ++i) if (s[i] == '?') id[i] = ++nodes;
    
    vector<int> stk(n + 1);
    for (int i = 1; i <= n; ++i) {
        if (s[i] != '(' && s[i] != ')') continue;
        
        if (!stk.empty() && s[stk.back()] == '(' && s[i] == ')') {
            other[stk.back()] = i;
            other[i] = stk.back();
            stk.pop_back();
        } else {
            stk.push_back(i);
        }
    }
    int rt = make_tree(1, n);
    
    S sol = dfs(rt);
    cout << sol.r - sol.l + 1 << "\n";
}

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