Submission #750140

#	Time	Username	Problem	Language	Result	Execution time	Memory
750140		inventiontime	Homework (CEOI22_homework)	C++17	100 / 100	357 ms	249232 KiB

Main

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

#define int ll
#define endl '\n' //comment for interactive
#define fast_io ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)

#define pb push_back
#define re resize
#define ff first
#define ss second

#define all(x) (x).begin(), (x).end()
#define all1(x) (x).begin()+1, (x).end()
#define loop(i, n) for(int i = 0; i < n; i++)
#define loop1(i, n) for(int i = 1; i <= n; i++)

#define print(x) cout << #x << ": " << x << endl << flush

typedef long long ll;
typedef vector<int> vi;
typedef array<int, 2> ii;
typedef array<int, 3> ti;
typedef vector<ii> vii;
typedef vector<ti> vti;
typedef vector<vi> vvi;
typedef priority_queue<int> pq;

template<class T> bool ckmin(T&a, T b) { bool B = a > b; a = min(a, b); return B; }
template<class T> bool ckmax(T&a, T b) { bool B = a < b; a = max(a, b); return B; }

const int inf = 1e17;

void solve() {

    string s;
    cin >> s;
    s = s + ' ';

    vi par(1), type(1);
    // ?    0
    // max +1
    // min -1

    int idx = 0, cnt = 0;
    stack<int> st;
    st.push(0);
    while(s[idx] != ' ') {
        if(s[idx] == 'm') {
            cnt++;
            type.pb(s[idx+1] == 'a' ? 1 : -1);
            par.pb(st.top());
            st.push(cnt);
            idx += 4;
        } else if(s[idx] == ')') {
            st.pop();
            idx++;
        } else if(s[idx] == '?') {
            cnt++;
            type.pb(0);
            par.pb(st.top());
            idx++;
        } else if(s[idx] == ',') {
            // do nothing
            idx++;
        }
    }

    vvi adj(cnt+1);
    loop1(i, cnt) {
        adj[par[i]].pb(i);
    }

    vi sub(cnt+1);
    vii intv(cnt+1);
    auto dfs = [&] (int u, auto dfs) -> void {
        if(type[u] == 0) {
            sub[u] = 1;
            intv[u] = {1, 1};
        } else {
            auto v1 = adj[u][0], v2 = adj[u][1];
            dfs(v1, dfs);
            dfs(v2, dfs);
            sub[u] = sub[v1] + sub[v2];
            auto [a, b] = intv[v1];
            auto [c, d] = intv[v2];
            int x1 = sub[v1], x2 = sub[v2];
            if(type[u] == -1) {
                intv[u] = {min(a, c), b + d - 1};
            } else {
                intv[u] = {a + c, x1 + x2 - min(x1 - b, x2 - d)};
            }
        }
    };
    dfs(1, dfs);

    cout << intv[1][1] - intv[1][0] + 1 << endl;

}

signed main() {

    fast_io;

    int t = 1; //cin >> t;
    while(t--)
        solve();

    return 0;

}

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