Submission #1226215

#	Time	Username	Problem	Language	Result	Execution time	Memory
1226215		trideser	Homework (CEOI22_homework)	C++20	100 / 100	192 ms	104004 KiB

Main

#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;	
}

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