Submission #1011200

#	Time	Username	Problem	Language	Result	Execution time	Memory
1011200		Forested	Homework (CEOI22_homework)	C++17	100 / 100	284 ms	186556 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using i32 = int;
using i64 = long long;
template <typename T>
using V = vector<T>;
template <typename T>
using VV = V<V<T>>;
#define OVERRIDE4(a, b, c, d, ...) d
#define REP2(i, n) for (i32 i = 0; i < (i32)(n); ++i)
#define REP3(i, l, r) for (i32 i = (i32)(l); i < (i32)(r); ++i)
#define REP(...) OVERRIDE4(__VA_ARGS__, REP3, REP2)(__VA_ARGS__)
#define PER2(i, n) for (i32 i = (i32)(n) - 1; i >= 0; --i)
#define PER3(i, l, r) for (i32 i = (i32)(r) - 1; i >= (i32)(l); --i)
#define PER(...) OVERRIDE4(__VA_ARGS__, PER3, PER2)(__VA_ARGS__)
#define LEN(x) (i32)size(x)
#define ALL(x) begin(x), end(x)
template <typename T>
bool chmin(T &x, const T &y) {
    if (x > y) {
        x = y;
        return true;
    }
    return false;
}
template <typename T>
bool chmax(T &x, const T &y) {
    if (x < y) {
        x = y;
        return true;
    }
    return false;
}

enum class Type {
    Question,
    Min,
    Max
};

struct Node {
    Type ty;
    Node *lch, *rch;
};

Node *parse(string &s, i32 &pos) {
    Node *ret = new Node;
    if (s[pos] == '?') {
        ++pos;
        ret->ty = Type::Question;
        ret->lch = nullptr;
        ret->rch = nullptr;
        return ret;
    }
    if (s[pos + 1] == 'i') {
        ret->ty = Type::Min;
    } else {
        ret->ty = Type::Max;
    }
    pos += 4;
    ret->lch = parse(s, pos);
    ++pos;
    ret->rch = parse(s, pos);
    ++pos;
    return ret;
}

// can make [low, high)
struct DP {
    i32 cnt, low, high;
};

DP dp(Node *node) {
    if (node->ty == Type::Question) {
        return DP{1, 0, 1};
    }
    DP ldp = dp(node->lch);
    DP rdp = dp(node->rch);
    DP ret;
    ret.cnt = ldp.cnt + rdp.cnt;
    if (node->ty == Type::Min) {
        ret.low = min(ldp.low, rdp.low);
        ret.high = ret.cnt - (ldp.cnt - ldp.high + rdp.cnt - rdp.high + 1);
    } else {
        ret.low = ldp.low + rdp.low + 1;
        ret.high = ret.cnt - min(ldp.cnt - ldp.high, rdp.cnt - rdp.high);
    }
    return ret;
}

int main() {
    string s;
    cin >> s;
    i32 n = count(ALL(s), '?');
    i32 pos = 0;
    Node *tree = parse(s, pos);
    DP d = dp(tree);
    i32 ans = d.high - d.low;
    cout << ans << '\n';
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:94:9: warning: unused variable 'n' [-Wunused-variable]
   94 |     i32 n = count(ALL(s), '?');
      |         ^

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