Submission #830391

#	Time	Username	Problem	Language	Result	Execution time	Memory
830391		peteza	Homework (CEOI22_homework)	C++14	53 / 100	133 ms	46824 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};
    queue<int> q; q.emplace(x);
    vector<int> dfss;
    while(!q.empty()) {
        if(type[q.front()] == type[x]) {
            q.push(bin[q.front()][0]);
            q.push(bin[q.front()][1]);
        } else dfss.push_back(q.front());
        q.pop();
    }
    int l, r;
    if(type[x] == 0) {
        l = INT_MAX; r = 0;
        for(int e:dfss) {
            pair<int, int> res = dfs(e);
            l = min(res.first, l);
            r += sz[e]-res.second+1;
        }        
        r = sz[x] - r + 1;
    } else {
        l = 0; r = INT_MAX;
        for(int e:dfss) {
            pair<int, int> res = dfs(e);
            l += res.first;
            r = min(sz[e]-res.second, r);
        }
        r = sz[x] - r;
    }
    //cout << x << " -> " << l << ' ' << r << '\n';
    return {l, r};
}


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:48:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |     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