Submission #750241

#	Time	Username	Problem	Language	Result	Execution time	Memory
750241		MetalPower	Homework (CEOI22_homework)	C++14	100 / 100	242 ms	205868 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define pii pair<int, int>
#define fi first
#define se second

const int MX = 2e6 + 10;

string s;

int tim = 0, tp[MX], lf[MX], rg[MX], sub[MX];
vector<int> st, adj[MX];

void dp(int idx){
	if(tp[idx] == 0){
		sub[idx] = lf[idx] = rg[idx] = 1;
	}else{
		for(int nxt : adj[idx]){
			dp(nxt);
			sub[idx] += sub[nxt];
		}
		if(tp[idx] == 1){ // max
			lf[idx] = lf[adj[idx][0]] + lf[adj[idx][1]];
			rg[idx] = max(sub[adj[idx][0]] + rg[adj[idx][1]], sub[adj[idx][1]] + rg[adj[idx][0]]);
		}else{ // min
			lf[idx] = min(lf[adj[idx][0]], lf[adj[idx][1]]);
			rg[idx] = rg[adj[idx][0]] + rg[adj[idx][1]] - 1;
		}
	}
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	cin >> s;

	for(int i = 0; i < (int) s.length(); ){
		if(s[i] == '(' || s[i] == ','){
			i++;
		}else if(s[i] == 'm'){
			if(s[i + 1] == 'a'){
				++tim;
				tp[tim] = 1;
				if(!st.empty()) adj[st.back()].push_back(tim);
				st.push_back(tim);
			}else{
				++tim;
				tp[tim] = 2;
				if(!st.empty()) adj[st.back()].push_back(tim);
				st.push_back(tim);
			}
			i += 3;
		}else if(s[i] == '?'){
			++tim;
			tp[tim] = 0;
			adj[st.back()].push_back(tim);
			i++;
		}else if(s[i] == ')'){
			st.pop_back();
			i++;
		}
	}

	dp(1);
	cout << rg[1] - lf[1] + 1 << '\n';
}

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