제출 #947500

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
947500		TAhmed33	Homework (CEOI22_homework)	C++98	100 / 100	279 ms	208528 KiB

Main

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e6 + 25;
string s; deque <char> a7a;
int cnt;
vector <int> adj[MAXN];
int type[MAXN];
stack <int> cur;
int dp[MAXN][2], sze[MAXN];
void dfs (int pos, int t, int par = -1) {
	if (type[pos] == 3) {
		dp[pos][0] = dp[pos][1] = 1;
		sze[pos] = 1;
		return;
	}
	for (auto j : adj[pos]) dfs(j, 3 - t, pos), sze[pos] += sze[j];
	if (type[pos] == 1) {
		dp[pos][0] = 1e9; dp[pos][1] = 1;
		for (auto j : adj[pos]) {
			dp[pos][0] = min(dp[pos][0], dp[j][0]);
			dp[pos][1] += dp[j][1] - 1;
		}
	} else {
		for (auto j : adj[pos]) {
			dp[pos][0] += dp[j][0];
			dp[pos][1] = max(dp[pos][1], sze[pos] - sze[j] + dp[j][1]);
		}
	}
	//cout << pos << ": " << t << " " << dp[pos][0] << " " << dp[pos][1] << '\n';
}
int main () {
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> s; 
	for (auto i : s) a7a.push_back(i); 
	int n = 0;
	while (!a7a.empty()) {
		if (a7a.front() == ',' || a7a.front() == '(') {
			a7a.pop_front(); continue;
		}
		if (a7a.front() == ')') {
			a7a.pop_front(); cur.pop(); continue;
		}
		if (a7a[0] == 'm' && a7a[1] == 'i' && a7a[2] == 'n') {
			if (!cur.empty()) {
				if (type[cur.top()] != 1) {
					++cnt; 
					adj[cur.top()].push_back(cnt);
					cur.push(cnt); 
					type[cnt] = 1;
				} else {
					cur.push(cur.top());
				}
			} else {
				++cnt; 
				cur.push(cnt); 
				type[cnt] = 1;
			}
			a7a.pop_front(); a7a.pop_front(); a7a.pop_front();
			continue;
		}
		if (a7a[0] == 'm' && a7a[1] == 'a' && a7a[2] == 'x') {
			if (!cur.empty()) {
				if (type[cur.top()] != 2) {
					++cnt; 
					adj[cur.top()].push_back(cnt);
					cur.push(cnt); 
					type[cnt] = 2;
				} else {
					cur.push(cur.top());
				}
			} else {
				++cnt; 
				cur.push(cnt); 
				type[cnt] = 2;
			}
			a7a.pop_front(); a7a.pop_front(); a7a.pop_front();
			continue;
		}
		if (a7a[0] == '?') {
			n++; ++cnt; 
			if (!cur.empty()) {
				adj[cur.top()].push_back(cnt);
			}
			type[cnt] = 3; a7a.pop_front(); continue;
		}
	}
	dfs(1, type[1]);
	cout << dp[1][1] - dp[1][0] + 1 << '\n';
}

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