Submission #1213090

#	Time	Username	Problem	Language	Result	Execution time	Memory
1213090		yanb	Homework (CEOI22_homework)	C++20	100 / 100	158 ms	166448 KiB

Main

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

using pii = pair<int, int>;
using t3i = tuple<int, int, int>;

struct Node {
    Node *l = nullptr, *r = nullptr, *p = nullptr;
    bool fmin, atom;
    int le, ge;

    Node() {}

    int parse(string &s, int cursor, vector<Node*> &atoms) {
        if (s[cursor] == '?') {
            atom = 1;
            atoms.push_back(this);
            return cursor + 1;
        } else {
            atom = 0;
            fmin = s[cursor + 2] == 'n';
            l = new Node(), r = new Node();
            l->p = this, r->p = this;
            cursor = l->parse(s, cursor + 4, atoms);
            return r->parse(s, cursor + 1, atoms) + 1;
        }
    }

    void run() {
        if (atom) {
            le = ge = 1;
        } else {
            l->run();
            r->run();
            if (fmin) {
                le = min(l->le, r->le);
                ge = l->ge + r->ge;
            } else {
                le = l->le + r->le;
                ge = min(l->ge, r->ge);
            }
        }
    }
};

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    
    string s;
    cin >> s;
    vector<Node*> atoms;
    Node *root = new Node();
    root->parse(s, 0, atoms);
    int n = atoms.size();
    root->run();
    cout << n + 2 - root->le - root->ge << "\n";
}

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