Submission #955146

#	Time	Username	Problem	Language	Result	Execution time	Memory
955146		PoPularPlusPlus	Homework (CEOI22_homework)	C++17	100 / 100	211 ms	183824 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define all(x) x.begin(),x.end()
#define vf first 
#define vs second
const int mod = 1000000007;

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

const int N = 2000009;

vector<pair<int,int>> adj[N];
int dp[N][2], siz[N];

void dfs(int node){
	if(adj[node].size() == 0){
		siz[node] = 1;
		dp[node][0] = dp[node][1] = 1;
		return;
	}
	siz[node] = 0;
	for(auto i : adj[node]){
		dfs(i.vf);
		siz[node] += siz[i.vf];
	}
	int u = adj[node][0].vf , v = adj[node][1].vf;
	if(adj[node][0].vs == 0){
		dp[node][0] = min(dp[u][0] , dp[v][0]);
		dp[node][1] = dp[v][1] + dp[u][1] - 1;
	}
	else {
		dp[node][0] = dp[u][0] + dp[v][0];
		dp[node][1] = max(siz[u] + dp[v][1] , siz[v] + dp[u][1]);
	}
}

void solve(){
	string s;
	cin >> s;
	int n = 0;
	int siz = s.size();
	for(int i = 0; i < siz; i++){
		if(s[i] == '?')
			n++;
	}
	stack<pair<int,int>> st;
	int cur = n;
	int cnt = 0;
	for(int i = 0; i < siz; i++){
		if(s[i] == 'm'){
			if(st.size()){
				int u = st.top().vf , w = st.top().vs, v = cur;
				st.pop();
				adj[u].pb(mp(v,w));
			}
			int w = 1;
			if(s[i + 1] == 'i')
				w = 0;
			st.push(mp(cur,w));
			st.push(mp(cur++,w));
		}
		else if(s[i] == '?'){
			int u = st.top().vf , w = st.top().vs, v = cnt++;
			st.pop();
			adj[u].pb(mp(v,w));
		}
	}
	dfs(n);
	cout << (dp[n][1] - dp[n][0]) + 1 << '\n';
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	//int t;cin>>t;
	//while(t--) 
	solve();
	return 0;
}

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