Submission #1133705

#	Time	Username	Problem	Language	Result	Execution time	Memory
1133705		steveonalex	Homework (CEOI22_homework)	C++20	100 / 100	89 ms	83648 KiB

Main

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

#define MASK(i) (1LL << (i))
#define GETBIT(mask, i) (((mask) >> (i)) & 1)
#define ALL(v) (v).begin(), (v).end()

ll max(ll a, ll b){return (a > b) ? a : b;}
ll min(ll a, ll b){return (a < b) ? a : b;}

ll gcd(ll a, ll b){return __gcd(a, b);}
ll LASTBIT(ll mask){return (mask) & (-mask);}
int pop_cnt(ll mask){return __builtin_popcountll(mask);}
int ctz(ll mask){return __builtin_ctzll(mask);}
int logOf(ll mask){return __lg(mask);}

mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
ll rngesus(ll l, ll r){return l + (ull) rng() % (r - l + 1);}

template <class T1, class T2>
    bool maximize(T1 &a, T2 b){
        if (a < b) {a = b; return true;}
        return false;
    }

template <class T1, class T2>
    bool minimize(T1 &a, T2 b){
        if (a > b) {a = b; return true;}
        return false;
    }

template <class T>
    void printArr(T& container, string separator = " ", string finish = "\n"){
        for(auto item: container) cout << item << separator;
        cout << finish;
    }


template <class T>
    void remove_dup(vector<T> &a){
        sort(ALL(a));
        a.resize(unique(ALL(a)) - a.begin());
    }

const int N = 2e6 + 69;
int cnt = 0, pos = 0;
int n = 0;
int type[N];
pair<int, int> graph[N];

void dfs(string &s, int u){
    graph[u] = {-1, -1};
    if (s[pos] == 'm'){
        type[u] = (s[pos+1] == 'a');
        pos += 3;

        pos++;
        graph[u].first = ++cnt;
        dfs(s, cnt);
        pos++;
        graph[u].second = ++cnt;
        dfs(s, cnt);
        pos++;
    }
    else{
        pos++;
        n++;
    }
}

int sz[N];

pair<int,int> go(int u){
    if (graph[u] == make_pair(-1, -1)){
        sz[u] = 1;
        return make_pair(1, 1);
    }
    pair<int, int> L = go(graph[u].first), R = go(graph[u].second);
    sz[u] = sz[graph[u].first] + sz[graph[u].second];
    if (type[u] == 0){ // min
        int mi = min(L.first, R.first);
        int ma = L.second + R.second - 1;
        return make_pair(mi, ma);
    }
    else{ // max
        int mi = sz[u] - ((sz[graph[u].first] - L.first) + (sz[graph[u].second] - R.first));
        int ma = max(L.second + sz[graph[u].second], R.second + sz[graph[u].first]);
        return make_pair(mi, ma);
    }
}

int main(void){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    clock_t start = clock();
    
    string s; cin >> s;
    dfs(s, 0);
    pair<int, int> ans = go(0);
    cout << ans.second - ans.first + 1 << "\n";

    cerr << "Time elapsed: " << clock() - start << "ms!\n";
    return 0;
}

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