Submission #1036900

#TimeUsernameProblemLanguageResultExecution timeMemory
1036900HorizonWestHomework (CEOI22_homework)C++17
13 / 100
177 ms178676 KiB
#include <iostream> #include <complex> #include <iomanip> #include <vector> #include <algorithm> #include <functional> #include <bitset> #include <queue> #include <map> #include <stack> #include <cmath> #include <cstdint> using namespace std; #define endl '\n' #define db double #define ll __int128 #define int long long #define pb push_back #define fs first #define sd second #define Mod long(1e9 + 7) #define all(x) x.begin(), x.end() #define unvisited long(-1) #define Eps double(1e-9) #define _for(i, n) for(int i = 0; i < (n); i++) #define dbg(x) cout << #x ": " << x << endl; const int Max = 1e6 + 7, Inf = 1e9 + 7; void print(bool x) { cout << (x ? "YES" : "NO") << endl; } string tostring (__int128 x) { string ans = ""; while(x > 0) { ans += (x % 10 + '0'); x /= 10; } reverse(all(ans)); return ans; } vector <vector<int>> v; vector <int> a; int n; pair <int, int> dfs(int node, int parent) { vector <pair<int, int>> s; pair <int, int> ans = { 0, 0 }; for(auto& u : v[node]) if(u != parent) { s.push_back(dfs(u, node)); } for(auto& u : s){ if(a[node] == 0){ ans.fs = min(u.fs, ans.fs); ans.sd = u.sd + ans.sd; } else{ ans.fs = u.fs + ans.fs; ans.sd = min(u.sd, ans.sd); } } if(a[node] == 0) ans.sd ++; else ans.fs ++; //cerr << node << " " << a[node] << " " << parent << " " << ans.fs << " " << ans.sd << endl; return ans; } void solve() { string s; cin >> s; vector <int> p; int node = 0; n = 0; v.push_back(vector<int> ()); p.push_back(-1); a.push_back(0); for(int i = 0; i < (int) s.size(); i++) { n += (s[i] == '?'); if(s[i] == 'm'){ if(node != 0) { v[node].push_back(v.size()); } a.push_back((s[i+1] == 'a')); p.push_back(node); node = v.size(); v.push_back(vector<int> ()); } if(s[i] == ')'){ node = p[node]; } } // cerr << n << endl; pair <int, int> ans = dfs(1, 0); cout << ((n - ans.sd) - ans.fs) << endl; } int32_t main() { ios_base::sync_with_stdio(0); cin.tie(0); int Q = 1; //cin >> Q; while (Q--) { solve(); } return 0; }
#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...