Submission #662022

#	Time	Username	Problem	Language	Result	Execution time	Memory
662022		Sohsoh84	Homework (CEOI22_homework)	C++17	100 / 100	291 ms	223428 KiB

Main

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;

#define all(x)			(x).begin(),(x).end()
#define X			first
#define Y			second
#define sep			' '
#define endl			'\n'
#define debug(x)		cerr << #x << ": " <<  x << endl;

const ll MAXN = 3e6 + 10;

// 0 -> ?, 1 -> min, 2 -> max
int n, p, T[MAXN], L[MAXN], R[MAXN], sz[MAXN];
string s;
vector<int> adj[MAXN];

inline char read() {
	return s[p++];
}

int build() {
	if (read() == '?') return ++n; // m / ?
	char t = read(); // i / a
	int v = ++n;

	T[v] = (t == 'i' ? 1 : 2);
	read(); // n / x
	read(); // (
	
	int a = build();
	read(); // ,
	int b = build();
	read(); // )
	
	adj[v].push_back(a);
	adj[v].push_back(b);
	return v;
}

void dfs(int v) {
	if (!T[v]) {
		L[v] = R[v] = sz[v] = 1;
		return;
	}

	int a = adj[v][0], b = adj[v][1];
	dfs(a);
	dfs(b);
	sz[v] = sz[a] + sz[b];

	if (T[v] == 2) {
		L[v] = L[a] + L[b];
		R[v] = max(R[a] + sz[b], R[b] + sz[a]);
	} else {
		R[v] = R[a] + R[b] - 1;
		L[v] = min(L[a], L[b]);
	}

}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> s;

	int v = build();
	dfs(v);

	cout << R[v] - L[v] + 1 << endl;
	return 0;
}

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