Submission #1323868

#TimeUsernameProblemLanguageResultExecution timeMemory
1323868WongYiKaiHomework (CEOI22_homework)C++20
100 / 100
294 ms222524 KiB
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const ll maxn = 2e6+5;

ll visited[maxn];
ll p[maxn];
vector<ll> adj[maxn];
pair<ll,ll> val[maxn];
ll state[maxn]; //0 -> min, 1 -> max, 2 -> ?
ll n=0;

void dfs(ll x){
    if (state[x]==2){
        val[x] = {1,n};
        return;
    }
    if (state[x]==0){
        ll l=n,r=n-1;
        for (ll nx:adj[x]){
            dfs(nx);
            r -= n-val[nx].second;
            l = min(l,val[nx].first);
        }
        val[x] = {l,r};
        return;
    }
    ll l=2,r=1;
    for (ll nx:adj[x]){
        dfs(nx);
        l += val[nx].first-1;
        r = max(r,val[nx].second);
    }
    val[x] = {l,r};
    return;
}

int main(){
    //ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    string s;
    cin >> s;
    p[0] = -1;
    ll cur = 0;
    ll pos = 0;
    ll idx = 0;
    vector<ll> leaf;
    while (pos < s.size()){
        if (s[pos]=='?'){
            state[cur] = 2;
            pos++;
            leaf.push_back(cur);
            n++;
        }
        else if (s[pos]=='m'){
            if (s[pos+1]=='a'){
                state[cur] = 1;
            }
            else state[cur] = 0;
            pos++;
        }
        else if (s[pos]=='('){
            idx++;
            p[idx] = cur;
            adj[cur].push_back(idx);
            cur = idx;
            pos++;
        }
        else if (s[pos]==','){
            cur = p[cur];
            idx++;
            p[idx] = cur;
            adj[cur].push_back(idx);
            cur = idx;
            pos++;
        }
        else if (s[pos]==')'){
            cur = p[cur];
            pos++;
        }
        else pos++;
    }
    dfs(0);
    //cout << val[0].first << ' ' << val[0].second;
    cout << val[0].second - val[0].first + 1;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...