Submission #716591

#	Time	Username	Problem	Language	Result	Execution time	Memory
716591		Arturgo	Homework (CEOI22_homework)	C++14	100 / 100	261 ms	149508 KiB

Main

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

struct Vertex {
	int type, l, r;
};

int root = -1;
vector<Vertex> vertices;

int N = 0;

int parse() {
	char car, useless;
	cin >> car;
	
	if(car == '?') {
		int id = vertices.size();
		vertices.push_back({0, -1, -1});
		N++;
		return id;
	}
	
	cin >> car;
	cin >> car;
	cin >> useless;
	int l = parse();
	cin >> useless;
	int r = parse();
	
	cin >> useless;
	int id = vertices.size();
	
	if(car == 'x') {
		vertices.push_back({1, l, r});
	}
	else {
		vertices.push_back({-1, l, r});
	}
	
	return id;
}

struct Ans {
	int lx_l, lx_g, gx_l, gx_g;
};

Ans dyn_ans[2000 * 1000];

Ans calcule_ans(int v) {
	Ans a;
	
	if(vertices[v].type == 0) {
		a = {1, 0, 0, 1};
	}
	else {
		Ans ans_l = calcule_ans(vertices[v].l);
		Ans ans_r = calcule_ans(vertices[v].r);
		
		if(vertices[v].type == 1) {
			a = {
				ans_l.lx_l + ans_r.lx_l,
				ans_l.lx_g + ans_r.lx_g,
				min(ans_l.gx_l, ans_r.gx_l),
				min(ans_l.gx_g, ans_r.gx_g)
			};
		} else {
			a = {
				min(ans_l.lx_l, ans_r.lx_l),
				min(ans_l.lx_g, ans_r.lx_g),
				ans_l.gx_l + ans_r.gx_l,
				ans_l.gx_g + ans_r.gx_g
			};
		}
	}
	
	return dyn_ans[v] = a;
}

/*void debug(int root) {
	if(vertices[root].type == 0) {
		cerr << "?";
		return;
	}
	
	if(vertices[root].type == 1) cerr << "max";
	else cerr << "min";
	
	cerr << "{";
	cerr << dyn_ans[root].lx_l << ",";
	cerr << dyn_ans[root].lx_g << ",";
	cerr << dyn_ans[root].gx_l << ",";
	cerr << dyn_ans[root].gx_g;
	cerr << "}";
	
	cerr << "(";
	debug(vertices[root].l);
	cerr << ",";
	debug(vertices[root].r);
	cerr << ")";
}*/

vector<pair<int, int>> inters;

void gen_inters(int v, int a = 0, int b = 0) {
	if(vertices[v].type == 0) {
		inters.push_back({a, N - b});
	}
	else {
		if(vertices[v].type == 1) {
			gen_inters(
				vertices[v].l,
				a + dyn_ans[vertices[v].r].lx_l,
				b + dyn_ans[vertices[v].r].lx_g
			);
			gen_inters(
				vertices[v].r,
				a + dyn_ans[vertices[v].l].lx_l,
				b + dyn_ans[vertices[v].l].lx_g
			);
		} else {
			gen_inters(
				vertices[v].l,
				a + dyn_ans[vertices[v].r].gx_l,
				b + dyn_ans[vertices[v].r].gx_g
			);
			gen_inters(
				vertices[v].r,
				a + dyn_ans[vertices[v].l].gx_l,
				b + dyn_ans[vertices[v].l].gx_g
			);
		}
	}
}


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	
	root = parse();
	calcule_ans(root);
	
	gen_inters(root);
	
	vector<int> vals(N + 1, 0);
	
	for(pair<int, int> inter : inters) {
		vals[inter.first]++;
		vals[inter.second]--;
	}
	
	int sum = 0;
	int nbPossibles = 0;
	
	for(int i = 0;i < N;i++) {
		sum += vals[i];
		if(sum > 0) nbPossibles++;
	}
	
	cout << nbPossibles << endl;
	
	return 0;
}

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