제출 #1111787

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1111787		MisterReaper	Homework (CEOI22_homework)	C++17	100 / 100	244 ms	191768 KiB

Main

#include <bits/stdc++.h>

using i64 = long long;

#ifdef DEBUG
    #include "debug.h"
#else
    #define debug(...) void(23)
#endif

constexpr int max_N = int(2E6) + 5;

int N;
std::vector<int> adj[max_N];
int tp[max_N], siz[max_N];

std::pair<int, int> dfs(int v) {
    debug(v, tp[v], adj[v]);
    if (tp[v] == 0) {
        return {0, 0};
    }
    int u0 = adj[v][0];
    int u1 = adj[v][1];
    auto r0 = dfs(u0);
    auto r1 = dfs(u1);
    siz[v] = siz[u0] + siz[u1];
    std::pair<int, int> res;
    if (tp[v] == -1) {
        res = {std::min(r0.first, r1.first), r0.second + r1.second};
    } else {
        res = {r0.first + r1.first + 1, std::max(r0.second + siz[u1], r1.second + siz[u0])};
    }
    debug(v, res);
    return res;
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr); 

    std::string S;
    std::cin >> S;

    int nv = 0;
    std::vector<int> stk;
    for (int i = 0; i < S.size(); ++i) {
        if (S[i] == '(') {
            tp[nv] = (S[i - 1] == 'n' ? -1 : +1);
            if (!stk.empty()) {
                adj[stk.back()].emplace_back(nv);
            }
            stk.emplace_back(nv++);
        } else if (S[i] == '?') {
            tp[nv] = 0;
            siz[nv] = 1;
            adj[stk.back()].emplace_back(nv++);
        } else if (S[i] == ')') {
            stk.pop_back();
        }
    }

    N = nv;

    auto x = dfs(0);
    std::cout << x.second - x.first + 1 << '\n';

    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

Main.cpp: In function 'int main()':
Main.cpp:46:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |     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