Submission #789140

#	Time	Username	Problem	Language	Result	Execution time	Memory
789140		ymm	Homework (CEOI22_homework)	C++17	100 / 100	150 ms	139364 KiB

Main

#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
typedef long long ll;
typedef std::pair<int,int> pii;
using namespace std;

struct node {
	int op;
	node *l, *r;
};

node *parse(string s)
{
	vector<node *> vec;
	vec.push_back(new node {-2, 0, 0});
	node **nxt = &vec.back()->l;
	int p = 0;
	while (p < s.size()) {
		if (s[p] == '?') {
			*nxt = new node {-1, 0, 0};
			nxt = &vec.back()->r;
			++p;
		} else if (s[p] == ',') {
			++p;
		} else if (s[p] == ')') {
			vec.pop_back();
			nxt = &vec.back()->r;
			++p;
		} else if (s[p+1] == 'i') {
			*nxt = new node {0, 0, 0};
			vec.push_back(*nxt);
			nxt = &vec.back()->l;
			p += 4;
		} else if (s[p+1] == 'a') {
			*nxt = new node {1, 0, 0};
			vec.push_back(*nxt);
			nxt = &vec.back()->l;
			p += 4;
		} else {
			assert(!"bad expression");
		}
	}
	auto ans = vec.back()->l;
	delete(vec.back());
	return ans;
}

tuple<int,int,int> solve(node *v)
{
	if (v->op == -1)
		return {0, 0, 1};
	auto [x1, y1, c1] = solve(v->l);
	auto [x2, y2, c2] = solve(v->r);
	if (v->op == 0)
		return {min(x1, x2), y1 + y2, c1 + c2};
	else
		return {x1 + x2 + 1, c1 + c2 - min(c1 - y1, c2 - y2), c1 + c2};
}

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	string s;
	cin >> s;
	node *v = parse(s);
	auto [x, y, cnt] = solve(v);
	cout << y-x+1 << '\n';
}

Compilation message (stderr)

Main.cpp: In function 'node* parse(std::string)':
Main.cpp:18:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |  while (p < s.size()) {
      |         ~~^~~~~~~~~~

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