Submission #1323911

#	Time	Username	Problem	Language	Result	Execution time	Memory
1323911		i271828	Homework (CEOI22_homework)	C++20	100 / 100	216 ms	171688 KiB

Main

#include <bits/stdc++.h>
#define pii pair<int,int>
#define ll long long
using namespace std;

const int MAX=3e6+5;
const int INF=1<<30;

int N;
string str;
int c=0;
vector<int> adj[MAX];
int T[MAX];
int D[MAX];

pii dfs(int x){
	if (T[x]==2){
		D[x]=1;
		return {0,0};
	}
	int a=adj[x][0],b=adj[x][1];
	auto [a0,a1]=dfs(a);
	auto [b0,b1]=dfs(b);
	D[x]=D[a]+D[b];
	if (T[x]==0) return {min(a0,b0),a1+b1};
	if (T[x]==1) return {a0+b0+1,D[x]-1-min(D[a]-1-a1,D[b]-1-b1)};
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);
	cin>>str;
	N=str.size();
	int l=0;
	vector<int> V;
	while (l<N){
		if (str[l]=='m'){
			l++;
			if (str[l]=='i'){
				T[c]=0;
			}
			if (str[l]=='a'){
				T[c]=1;
			}
			if (V.size()) adj[V.back()].push_back(c);
			V.push_back(c);
			c++;
			l++;
		}else if (str[l]=='?'){
			T[c]=2;
			if (V.size()) adj[V.back()].push_back(c);
			c++;
		}else if (str[l]==')') V.pop_back();
		l++;
	}
	N=c;
	auto [a,b]=dfs(0);
	cout<<b-a+1<<'\n';
}

Compilation message (stderr)

Main.cpp: In function 'std::pair<int, int> dfs(int)':
Main.cpp:27:1: warning: control reaches end of non-void function [-Wreturn-type]
   27 | }
      | ^

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