Submission #1006359

#TimeUsernameProblemLanguageResultExecution timeMemory
1006359aykhnHomework (CEOI22_homework)C++17
53 / 100
13 ms15844 KiB
#include <bits/stdc++.h> using namespace std; #define inf 0x3F3F3F3F const int MXN = 5e3 + 5; int n, r, cnt; string s; int adj[MXN][2]; array<int, 2> dp[MXN]; int sz[MXN]; int t[MXN]; vector<int> R; array<int, 2> MERGE(array<int, 2> x, array<int, 2> y) { return {min(x[0], y[0]), max(x[1], y[1])}; } void dfs(int a) { if (t[a] == 2) { dp[a] = {1, 1}; sz[a] = 1; return; } dfs(adj[a][0]), dfs(adj[a][1]); if (t[a] == 1) { dp[a] = MERGE({dp[adj[a][0]][0] + dp[adj[a][1]][0], dp[adj[a][0]][1] + sz[adj[a][1]]}, {dp[adj[a][1]][0] + dp[adj[a][0]][0], dp[adj[a][1]][1] + sz[adj[a][0]]}); } else { dp[a] = MERGE({dp[adj[a][0]][0], dp[adj[a][0]][1] + dp[adj[a][1]][1] - 1}, {dp[adj[a][1]][0], dp[adj[a][1]][1] + dp[adj[a][0]][1] - 1}); } sz[a] = sz[adj[a][0]] + sz[adj[a][1]]; } signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> s; n = s.length(); string nw; for (int i = 0; i < s.length(); i++) { if (s[i] == ',') continue; if (s[i] == '?') { t[nw.size()] = 2; nw.push_back('('); nw.push_back(')'); } else if (s[i] == '(' || s[i] == ')') nw.push_back(s[i]); else { if (s[i + 1] == 'i') t[nw.size()] = 0; else t[nw.size()] = 1; i += 2; } } vector<int> v; R.assign(nw.size(), 0); for (int i = (int)nw.size() - 1; i >= 0; i--) { if (nw[i] == ')') v.push_back(i); else R[i] = v.back(), v.pop_back(); } v.clear(); for (int i = (int)nw.size() - 1; i >= 0; i--) { if (nw[i] == '(') { vector<int> tmp; while (!v.empty() && v.back() <= R[i]) tmp.push_back(v.back()), v.pop_back(); assert(tmp.size() == 2 || tmp.empty()); v.push_back(i); if (tmp.size() == 2) { adj[i][0] = tmp[0], adj[i][1] = tmp[1]; } } } assert(v.size() == 1); dfs(v[0]); cout << dp[v[0]][1] - dp[v[0]][0] + 1 << '\n'; }

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:49:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |   for (int i = 0; i < s.length(); 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...