Submission #839173

#	Time	Username	Problem	Language	Result	Execution time	Memory
839173		dolphingarlic	Homework (CEOI22_homework)	C++17	100 / 100	267 ms	160792 KiB

Main

#include <bits/stdc++.h>
using namespace std;

const int N = 2000001;

vector<int> graph[N];
int p[N], n = 0, type[N], sz[N], mn[N], mx[N];

void dfs(int node = 1) {
	if (!graph[node].size()) return;
	int u = graph[node][0], v = graph[node][1];
	dfs(u);
	dfs(v);
	sz[node] += sz[u] + sz[v];
	if (type[node] == 1) {  // min
		mn[node] = min(mn[u], mn[v]);
		mx[node] = mx[u] + mx[v] - 1;
	} else if (type[node] == 2) {  // max
		mn[node] = mn[u] + mn[v];
		mx[node] = max(sz[u] + mx[v], sz[v] + mx[u]);
	}
}
 
int main() {
	string s;
	cin >> s;
	int curr = 0;
	for (int i = 0; i < s.size(); i++) {
		if (s[i] == 'm') {
			p[++n] = curr;
			graph[curr].push_back(n);
			curr = n;
			if (s[i + 2] == 'n') type[curr] = 1;  // min
			else type[curr] = 2;  // max
			i += 3;
		} else if (s[i] == '?') {
			p[++n] = curr;
			graph[curr].push_back(n);
			curr = n;
			mn[curr] = mx[curr] = sz[curr] = 1;
		} else curr = p[curr];
	}
	dfs();
	cout << mx[1] - mn[1] + 1;
	return 0;
}

Compilation message (stderr)

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

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