Submission #731208

#	Time	Username	Problem	Language	Result	Execution time	Memory
731208		minhcool	Homework (CEOI22_homework)	C++17	100 / 100	213 ms	61008 KiB

Main

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

//#define int long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair

typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;

const int N = 2e6 + 5;

const int oo = 1e18 + 7, mod = 1e9 + 7;

bool mx[N];
ii children[N];

int cnt = 1;

int n;

void dfs(int node){
	char c;
	cin >> c;
	if(c == '?'){
		n++;
		return;
	}
	cin >> c >> c;
	mx[node] = (c == 'x');
	cin >> c;
	cnt++;
	children[node].fi = cnt;
	dfs(cnt);
	cin >> c;
	cnt++;
	children[node].se = cnt;
	dfs(cnt);
	cin >> c;
}

int get(int node){
	if(!children[node].fi) return 1;
	int temp1 = get(children[node].fi), temp2 = get(children[node].se);
	if(mx[node]) return temp1 + temp2;
	else return min(temp1, temp2);
}

void process(){
	dfs(1);
	int answer = n + 2;
	answer -= get(1);
	for(int i = 1; i <= cnt; i++) mx[i] ^= 1;
	answer -= get(1);
	cout << answer << "\n";
}

signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	process();
}

Compilation message (stderr)

Main.cpp:16:21: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   16 | const int oo = 1e18 + 7, mod = 1e9 + 7;
      |                ~~~~~^~~

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