Submission #830397

#	Time	Username	Problem	Language	Result	Execution time	Memory
830397		peteza	Homework (CEOI22_homework)	C++14	100 / 100	63 ms	58208 KiB

Main

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

string str;
int bin[5000005][2];
int type[5000005], sz[5000005];
int cnode = 0;
stack<int> stk;
pair<int, int> dp[5000005];

int main() {
    cin.tie(0) -> sync_with_stdio(0);
    cin >> str; 
    for(int i=0;i<str.size();) {
        if(str[i] == ',' || str[i]=='('){i++; continue;}
        if(str[i] == 'm') {
            stk.push(cnode);
            if(str[i+1] == 'i') { //minimum
                type[cnode++] = 0;
            } else {
                type[cnode++] = 1;
            }
            i += 4;
        } else if(str[i] == '?') {
            stk.push(cnode); sz[cnode] = 1;
            dp[cnode] = {1, 1};
            type[cnode++] = 2;
            i++;
        } else {
            int e1 = stk.top(); stk.pop();
            int e2 = stk.top(); stk.pop();
            bin[stk.top()][0] = e2; bin[stk.top()][1] = e1;
            sz[stk.top()] = sz[e1] + sz[e2];
            int x = stk.top();
            if(type[x] == 0) {
                auto r1 = dp[bin[x][0]], r2 = dp[bin[x][1]];
                dp[x] = {min(r1.first, r2.first), sz[x]+1-(sz[bin[x][0]]+sz[bin[x][1]]-r1.second-r2.second+2)};
            } else {
                auto r1 = dp[bin[x][0]], r2 = dp[bin[x][1]];
                dp[x] = {r1.first + r2.first, sz[x]-min(sz[bin[x][0]]-r1.second, sz[bin[x][1]]-r2.second)};
            }
            i++;
        }
    }
    cout << dp[0].second-dp[0].first+1;
}

// min(max(max(?,?),max(?,?)),min(max(?,?),max(?,?)))

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:14:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |     for(int i=0;i<str.size();) {
      |                 ~^~~~~~~~~~~

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