Submission #1226215

#TimeUsernameProblemLanguageResultExecution timeMemory
1226215trideserHomework (CEOI22_homework)C++20
100 / 100
192 ms104004 KiB
#include <bits/stdc++.h>
using namespace std;

int rec(string& s, int& index, vector<tuple<char, int, int>>& ops) {
	//cerr << "REC: " << index << "\n";
	for(int i = index; i < s.size(); i++) {
		//cerr << s[i];
	}
	//cerr << "\n";


	char op = s[index + 2];
	int lchild;
	int rchild;
	index += 4;
	//cerr << "\t" << s[index] << "\n";
	if(s[index] == 'm') {
		lchild = rec(s, index, ops);
	}
	else {
		lchild = -1;
		index++;
	}
	index++;

	//cerr << "\t" << s[index] << "\n";
	if(s[index] == 'm') {
		rchild = rec(s, index, ops);
	}
	else {
		rchild = -1;
		index++;
	}
	index++;
	//cerr << "\n\n";
	ops.push_back(make_tuple(op, lchild, rchild));
	return ops.size() - 1;
}

pair<int, int> get_size(vector<tuple<char, int, int>>& ops, int node) {
	if(node == -1) {
		return make_pair(0, 0);
	}
	//cerr << node << "<\n";
	pair<int, int> left = get_size(ops, get<1>(ops[node]));
	pair<int, int> right = get_size(ops, get<2>(ops[node]));
	if(get<0>(ops[node]) == 'x') {
		return make_pair(left.first + right.first + 1, min(left.second, right.second));
	}
	else {
		return make_pair(min(left.first, right.first), left.second + right.second + 1);
	}

}

int main() {
	string input;
	cin >> input;
	//cerr << input << "\n";
	vector<tuple<char, int, int>> ops;
	int ix = 0;
	rec(input, ix, ops);
	
	//cerr << "OPS:\n\n";
	for(tuple<char, int, int> t : ops) {
		//cerr << get<0>(t) << " " << get<1>(t) << " " << get<2>(t) << "\n";
	}
	pair<int, int> sz = get_size(ops, ops.size() - 1);
	cout << ops.size() + 1 - sz.first - sz.second;
	
	
	return 0;	
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...