Submission #632117

#	Time	Username	Problem	Language	Result	Execution time	Memory
632117		drkarlicio2107	Homework (CEOI22_homework)	C++14	23 / 100	1085 ms	524288 KiB

Main

#include <bits/stdc++.h>
using namespace std;
int ind=0;
int t [2000010];
vector <int> g [2000010]; int n=0; int maxi=0;
void rec (string s, int i, int par){
	maxi=max (maxi, i);
	//cout << i << endl;
	if (s [i]=='?'){
		t [ind]=2;
		g [par].push_back (ind);
		ind++; n++;
	}
	if (s [i+1]=='i'){
		t [ind]=0;
		g [par].push_back (ind);
		ind++;
		rec (s, i+4, ind-1);
	}
	if (s [i+1]=='a'){
		t [ind]=1;
		g [par].push_back (ind);
		ind++;
		rec (s, i+4, ind-1);
	}
	if (i==0) return ;
	i=maxi;
	//cout << maxi << endl;
	while (s [i]!=',') i++;
	i++;
	//cout << i << " " << ind << endl;
	maxi=max (maxi, i);
	if (s [i]=='?'){
		t [ind]=2;
		g [par].push_back (ind);
		ind++; n++;
	}
	if (s [i+1]=='i'){
		t [ind]=0;
		g [par].push_back (ind);
		ind++;
		rec (s, i+4, ind-1);
	}
	if (s [i+1]=='a'){
		t [ind]=1;
		g [par].push_back (ind);
		ind++;
		rec (s, i+4, ind-1);
	}
	return ;
}
pair <int, int> sol (int x){
	//cout << x;
	if (t [x]==2) return {1, n};
	if (t [x]==1) return {sol (g[x][0]).first+sol (g[x][1]).first, max (sol (g[x][0]).second, sol (g[x][1]).second)};
	return {min (sol (g[x][0]).first, sol (g[x][1]).first), sol (g[x][0]).second+sol (g[x][1]).second-n-1};
}
int main(){
	string s; cin >> s;
	rec (s, 0, 2000001);
	//cout << g [0].size();
	cout << sol (0).second-sol (0).first+1;
	return 0;
}

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