Submission #792409

#	Time	Username	Problem	Language	Result	Execution time	Memory
792409		t6twotwo	Homework (CEOI22_homework)	C++17	100 / 100	200 ms	169924 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s;
    cin >> s;
    int M = 0, N = 0;
    vector<int> l, r, q, stk, t(s.size());
    for (int i = 0; i < s.size(); i++) {
        if (isalpha(s[i])) {
            continue;
        }
        if (s[i] == '?') {
            l.push_back(-1);
            r.push_back(-1);
            q.push_back(-1);
            N++;
            t[i] = M++;
        } else if (s[i] == '(') {
            stk.push_back(i);
        } else if (s[i] == ',') {
            int j = stk.back();
            t[j] = t[i - 1];
        } else if (s[i] == ')') {
            int j = stk.back();
            stk.pop_back();
            l.push_back(t[j]);
            r.push_back(t[i - 1]);
            q.push_back(s[j - 1] == 'x' ? 1 : 0);
            t[i] = M++;
        }
    }
    vector<int> lo(M), hi(M);
    auto dfs = [&](auto dfs, int x) -> void {
        if (l[x] == -1) {
            return;
        };
        dfs(dfs, l[x]);
        dfs(dfs, r[x]);
        if (q[x] == 0) {
            lo[x] = lo[l[x]] + lo[r[x]] + 1;
            hi[x] = min(hi[l[x]], hi[r[x]]);
        } else {
            lo[x] = min(lo[l[x]], lo[r[x]]);
            hi[x] = hi[l[x]] + hi[r[x]] + 1;
        }
    };
    dfs(dfs, M - 1);
    cout << N - lo[M - 1] - hi[M - 1] << "\n";
    return 6/22;
}

Compilation message (stderr)

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

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