Submission #710770

#	Time	Username	Problem	Language	Result	Execution time	Memory
710770		Jarif_Rahman	Homework (CEOI22_homework)	C++17	100 / 100	317 ms	217840 KiB

Main

#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;

str s;
int n = 1, m;
vector<int> type(1, -1);
vector<int> L(1, -1), R(1, -1);
vector<int> leaves;
vector<vector<int>> dp;
vector<int> sum;

int create_tree(int nd, int i){
    if(s[i] == '?'){
        leaves.pb(nd);
        return i;
    }
    if(s[i+1] == 'i') type[nd] = 0;
    else type[nd] = 1;

    L.pb(-1);
    R.pb(-1);
    type.pb(-1);
    L[nd] = n;
    n++;

    int x = create_tree(L[nd], i+4);
    x+=2;

    L.pb(-1);
    R.pb(-1);
    type.pb(-1);
    R[nd] = n;
    n++;

    x = create_tree(R[nd], x);

    return x+1;
}

void pre_dfs(int nd){
    if(type[nd] == -1){
        dp[nd][0] = 1;
        dp[nd][1] = 1;
        return;
    }
    pre_dfs(L[nd]);
    pre_dfs(R[nd]);

    // want smaller (dp[nd][0])
    if(type[nd] == 0) dp[nd][0] = min(dp[L[nd]][0], dp[R[nd]][0]);
    else dp[nd][0] = dp[L[nd]][0] + dp[R[nd]][0];

    // want larger (dp[nd][1])
    if(type[nd] == 0) dp[nd][1] = dp[L[nd]][1] + dp[R[nd]][1];
    else dp[nd][1] = min(dp[L[nd]][1], dp[R[nd]][1]);
}

void dfs(int nd, int a = 0, int b = 0){
    if(type[nd] == -1){
        if(a+b < m) sum[a]++, sum[m-b]--;
        return;
    }

    if(type[nd] == 0){
        dfs(L[nd], a, b+dp[R[nd]][1]);
        dfs(R[nd], a, b+dp[L[nd]][1]);
    }
    else{
        dfs(L[nd], a+dp[R[nd]][0], b);
        dfs(R[nd], a+dp[L[nd]][0], b);
    }
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> s;
    create_tree(0, 0);

    dp.assign(n, vector<int>(2, n));
    m = leaves.size();
    sum.assign(m+1, 0);

    pre_dfs(0);
    dfs(0);

    int ans = 0;
    for(int i = 0; i < m; i++){
        if(i) sum[i]+=sum[i-1];
        if(sum[i] > 0) ans++;
    }

    cout << ans << "\n";
}

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