Submission #1138769

#	Time	Username	Problem	Language	Result	Execution time	Memory
1138769		bilgun	Homework (CEOI22_homework)	C++20	0 / 100	350 ms	589824 KiB

Main

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

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

void dfs( int i){
	if( !graph[i].size()) return;
	int u = graph[i][0], v = graph[i][1];
	dfs(u);
	dfs(v);
	sz[i] += sz[u] + sz[v];
	if( type[i] == 1){
		mn[i] = min( mn[u], mn[v]);
		mx[i] = mx[u] + mx[v] - 1;
	}
	else if( type[i] == 2){
		mn[i] = mn[u] + mn[v];
		mx[i] = 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'){
			n++;
			par[n] = curr;
			graph[curr].push_back(n);
			curr = n;
			if( s[i + 2] == 'n') type[curr] = 1;
			else type[curr] = 2;
			i+=3;
		}
		else if( s[i] == '?'){
			n++;
			graph[curr].push_back(n);
			curr = n;
			mn[curr] = mx[curr] = sz[curr] = 1;
		} else {
			curr = par[curr];
		}
	}
	dfs(1);
	cout << mx[1] - mn[1] + 1;
	return 0;
}

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