# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
618045 | 2022-08-01T20:13:20 Z | czhang2718 | HicCup (FXCUP4_hiccup) | C++17 | 0 ms | 0 KB |
// #include "hiccup.h" using namespace std; #include "bits/stdc++.h" const int N=1e6+1; vector<int> adj[N]; int cnt[N]; int ans; bool bad; void dfs(int x){ int e=0, c=0; for(int i=adj[x].size()-1; i>=0; i--){ int k=adj[x][i]; e+=cnt[k]; c++; ans=min(ans, e/c); dfs(k); } } int HicCup(std::string S) { int n = S.size(); ans=1e9; S='-'+S; stack<int> par; par.push(0); int prv=-1; for(int i=1; i<=n; i++){ if(S[i]=='!'){ if(prv==-1 || S[i-1]=='H') return -1; cnt[prv]++; continue; } if(S[i]=='C'){ if(par.size()<2) return -1; int p=par.top(); par.pop(); prv=p; adj[par.top()].push_back(p); } else{ par.push(i); } } // for(int i=0; i<=n; i++){ // if(cnt[i]) cout << "cnt[" << i << "] " << cnt[i] << "\n"; // } if(par.size()!=1) return -1; dfs(0); return ans; } int main(){ string s; cin >> s; cout << HicCup(s); }