Submission #830393

#	Time	Username	Problem	Language	Result	Execution time	Memory
830393		peteza	Homework (CEOI22_homework)	C++14	53 / 100	135 ms	46564 KiB

Main

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

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

int ci = 0;

pair<int, int> dfs(int x) {
    if(type[x] == 2) return {1, 1};
    if(type[x] == 0) {
        auto r1 = dfs(bin[x][0]), r2 = dfs(bin[x][1]);
        return {min(r1.first, r2.first), sz[x]+1-(sz[bin[x][0]]+sz[bin[x][1]]-r1.second-r2.second+2)};
    } else {
        auto r1 = dfs(bin[x][0]), r2 = dfs(bin[x][1]);
        return {r1.first + r2.first, sz[x]-min(sz[bin[x][0]]-r1.second, sz[bin[x][1]]-r2.second)};
    }
}


int main() {
    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;
            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];
            i++;
        }
    }
    pair<int, int> res = dfs(0);
    cout << res.second - res.first + 1;
}

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

Compilation message (stderr)

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

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