Submission #966913

#	Time	Username	Problem	Language	Result	Execution time	Memory
966913		yellowtoad	Homework (CEOI22_homework)	C++17	100 / 100	306 ms	163016 KiB

Main

#include <iostream>
#include <vector>
#define f first
#define s second
using namespace std;

string s;
int op[2000010], cnt, n;
pair<int,int> node[2000010];
vector<int> edge[2000010], stk;

void dfs(int u) {
	for (int i = 0; i < edge[u].size(); i++) dfs(edge[u][i]);
	if (edge[u].size() == 2) {
		if (op[u]) node[u] = {min(node[edge[u][0]].f,node[edge[u][1]].f),node[edge[u][0]].s+node[edge[u][1]].s+1};
		else node[u] = {node[edge[u][0]].f+node[edge[u][1]].f+1,min(node[edge[u][0]].s,node[edge[u][1]].s)};
	} else n++;
}

int main() {
	cin >> s;
	stk.push_back(0);
	for (int i = 0; i < s.length(); i++) {
		if (s[i] == 'm') {
			++cnt;
			if (s[i+1] == 'a') op[cnt] = 1;
			edge[stk.back()].push_back(cnt);
			stk.push_back(cnt);
			i += 3;
		} else if (s[i] == '?') edge[stk.back()].push_back(++cnt);
		else if (s[i] == ')') stk.pop_back();
	}
	dfs(1);
	cout << n-node[1].f-node[1].s << endl;
}

Compilation message (stderr)

Main.cpp: In function 'void dfs(int)':
Main.cpp:13:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |  for (int i = 0; i < edge[u].size(); i++) dfs(edge[u][i]);
      |                  ~~^~~~~~~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:23:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |  for (int i = 0; i < s.length(); i++) {
      |                  ~~^~~~~~~~~~~~

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