Submission #1105449

#	Time	Username	Problem	Language	Result	Execution time	Memory
1105449		epicci23	Homework (CEOI22_homework)	C++17	100 / 100	142 ms	127424 KiB

Main

#include "bits/stdc++.h"
//#define int long long
#define all(v) v.begin() , v.end()
#define sz(a) (int)a.size()
using namespace std;

const int N = 2e6 + 5;
int dp[N][2],val[N],kid[N][2],p=3;

void dfs(int c){
  if(val[c]==0){
    dp[c][0]=dp[c][1]=1;
    return;
  }
  int a=kid[c][0],b=kid[c][1];
  dfs(a),dfs(b);
  if(val[c]==1){ // min
    dp[c][0]=min(dp[a][0],dp[b][0]);
    dp[c][1]=dp[a][1]+dp[b][1];
  }
  else{ // max 
    dp[c][0]=dp[a][0]+dp[b][0];
    dp[c][1]=min(dp[a][1],dp[b][1]);
  }
}


void _(){
 string s;
 cin >> s;
 int n = sz(s);
 int M = count(all(s),'?');
 vector<int> ar;
 for(int i=0;i<n;){
   if(s[i]==','){
   	i++;
   	continue;
   }
   if(s[i]=='m'){
   	 if(s[i+1]=='a') ar.push_back(2);
   	 else ar.push_back(1);
   	 i+=4;
   	 continue;
   }
   if(s[i]==')'){
     ar.push_back(-1);
     i++;
     continue;
   }
   if(s[i]=='?'){
     ar.push_back(p++);
     i++;
     continue;
   }
   i++;
 }
 stack<int> st;
 for(int x:ar){
   st.push(x);
   if(st.top()==-1){
   	 st.pop();
   	 int a = st.top();
   	 st.pop();
   	 int b = st.top();
   	 st.pop();
   	 int c = p++;
     kid[c][0]=a;
     kid[c][1]=b;
     val[c]=st.top();
     st.pop();
     st.push(c);
   }
 }
 int rt = st.top();
 st.pop();
 dfs(rt);
 int r =  M - dp[rt][1] + 1;
 int l = dp[rt][0];
 cout << r-l+1 << '\n';
}

int32_t main(){
  cin.tie(0); ios::sync_with_stdio(0);
  int tc=1;//cin >> tc;
  while(tc--) _();
  return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 13 / 13
• Subtask 3: 13 / 13
• Subtask 4: 30 / 30
• Subtask 5: 34 / 34