Submission #1111787

#TimeUsernameProblemLanguageResultExecution timeMemory
1111787MisterReaperHomework (CEOI22_homework)C++17
100 / 100
244 ms191768 KiB
#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; }

Compilation message (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) {
      |                     ~~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...