Submission #1014799

#	Time	Username	Problem	Language	Result	Execution time	Memory
1014799		atom	Homework (CEOI22_homework)	C++17	100 / 100	192 ms	186412 KiB

Main

#include "bits/stdc++.h"
// @JASPER'S BOILERPLATE
using namespace std;
using ll = long long;

#ifdef JASPER
#include "debug.h"
#else
#define debug(...) 166
#endif

const int N = 1e6 + 5;

int n, sz;
string s; 
vector <int> c;

struct Node {
    int t;
    Node *l, *r;
};

Node* make(int& i) {
    Node* cur = new Node;
    if (s[i] == '?') {
        ++i;
        cur->t = 0;
        cur->l = cur->r = nullptr;
        return cur;
    }    

    if (s[i + 1] == 'i') {
        cur->t = -1;
    }
    else {
        cur->t = -2;
    }
    i += 4;
    cur->l = make(i);
    ++i;
    cur->r = make(i);
    ++i;

    return cur;
}
using T = array <int, 3>;
// cnt, up, lo;
T solve(Node* tr) {
    if (tr->t == 0) return {1, 0, 1};
    
    T ql = solve(tr->l);
    T qr = solve(tr->r);
    T res;
    res[0] = ql[0] + qr[0];
    if (tr->t == -1) {
        res[1] = min(ql[1], qr[1]);
        res[2] = ql[2] + qr[2] - 1;
    }
    else {
        res[1] = ql[1] + qr[1] + 1;
        res[2] = res[0] - min(ql[0] - ql[2], qr[0] - qr[2]);
    }
    return res;
}


signed main() {
    cin.tie(0) -> sync_with_stdio(0);
    
    #ifdef JASPER
        freopen("in1", "r", stdin);
    #endif

    cin >> s;
    sz = s.size();
    
    int p = 0;
    Node* tr = make(p);
    T ans = solve(tr);
    cout << (ans[2] - ans[1]) << "\n";

    // if (n >= 9) {
    //     c.resize(n);
    //     iota(c.begin(), c.end(), 1);

    //     vector <int> vals;
    //     do {
    //         vals.push_back(dfs(tr));
    //     } while (next_permutation(c.begin(), c.end()));

    //     sort(vals.begin(), vals.end());
    //     vals.resize(unique(vals.begin(), vals.end()) - vals.begin());

    //     cout << dfs(tr) << "\n";
    // }
    // else {
    //     debug(n);
    //     T ans = solve(tr);
    //     // debug(ans);
    //     // cout << (ans[2] - ans[1] + 1) << "\n";
    // }

    return 0;
}

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