Submission #1127002

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127002		Icelast	Homework (CEOI22_homework)	C++20	23 / 100	604 ms	418456 KiB

Main

#include <iostream>
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn = 2*1e5+5, INF = 4e18+9;
void sub1(int n, int c, vector<vector<int>> adj, vector<int> t){
    vector<int> p(n+1);
    iota(p.begin()+1, p.end(), 1);
    vector<int> ans(n+1, 0);
    do{
        vector<ll> f(c+1, 0);
        int cnt = 0;
        auto dfs = [&](auto dfs, int u, int pa) -> void{
            if(adj[u].size() == 1){
                cnt++;
                f[u] = p[cnt];
            }else{
                if(t[u] == 1){
                    f[u] = -INF;
                }else{
                    f[u] = INF;
                }
            }
            for(int v : adj[u]){
                if(v == pa) continue;
                dfs(dfs, v, u);
                if(t[u] == 1){
                    f[u] = max(f[u], f[v]);
                }else{
                    f[u] = min(f[u], f[v]);
                }
            }
        };
        dfs(dfs, 1, 0);
        ans[f[1]] = 1;
    }while(next_permutation(p.begin()+1, p.end()));
    int res = 0;
    for(int i = 1; i <= n; i++){
        if(ans[i]){
            res++;
        }
    }
    cout << res;
}
void subfull(int n, int c, vector<vector<int>> adj, vector<int> t){
    vector<pair<int, int>> f(c+1);
    vector<int> sub(c+1, 0);
    auto dfs = [&](auto dfs, int u, int p) -> void{
        if(adj[u].size() == 1){
            f[u] = {1, 1};
            sub[u] = 1;
            return;
        }
        pair<int, int> cur = {-1, -1}, fin;
        int subcur;
        for(int v : adj[u]){
            if(v == p) continue;
            dfs(dfs, v, u);
            sub[u] += sub[v];
            if(cur.first == -1){
                cur = f[v];
                subcur = sub[v];
            }else{
                if(t[u] == -1){
                    fin.first = min(cur.first, f[v].first);
                    fin.second = max(cur.second+f[v].first-1, f[v].second+cur.first-1);
                }else{
                    fin.first = cur.first+f[v].first;
                    fin.second = max(cur.second+sub[v], f[v].second+subcur);
                }
            }
        }
        f[u] = fin;
    };
    dfs(dfs, 1, 0);
    cout << f[1].second-f[1].first+1;
}
void solve(){
    string s;
    cin >> s;
    if((int)s.size() == 1){
        cout << 1;
        return;
    }
    int i = 0;
    vector<int> t(1);
    vector<int> st(1, 0);
    int c = 0;
    vector<int> pa(1);
    int n = 0;
    while(i < (int)s.size()){
        if(s[i] == 'm'){
            if(s[i+1] == 'i'){
                c++;
                pa.push_back(st.back());
                t.push_back(-1);
                st.push_back(c);
            }else if(s[i+1] == 'a'){
                c++;
                t.push_back(1);
                pa.push_back(st.back());
                st.push_back(c);
            }
            i+=4;
            continue;
        }else if(s[i] == '?'){
            c++;
            n++;
            t.push_back(0);
            pa.push_back(st.back());
            i++;
            continue;
        }
        if(s[i] == ')'){
            st.pop_back();
            i++;
            continue;
        }
        if(s[i] == ','){
            i++;
            continue;
        }
    }
    vector<vector<int>> adj(c+1);
    for(int i = 1; i <= c; i++){
        adj[i].push_back(pa[i]);
        adj[pa[i]].push_back(i);
    }
    if(n <= 9){
        sub1(n, c, adj, t);
        return;
    }
    subfull(n, c, adj, t);
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    //freopen("MINMAX.inp", "r", stdin);
    //freopen("MINMAX.out", "w", stdout);
    solve();
}

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