Problema con "Alberi"

Aiuto
1

Stavo risolvendo il problema alberi (https://training.olinfo.it/#/task/alberi/statement).
Ma, con questo codice, ottengo solo 30/100 con i restanti testcase che falliscono per “Execution killed with signal 11”:

#include <bits/stdc++.h>
#define all(X) (X).begin(),(X).end()
#define rall(X) (X).rbegin(),(X).rend()
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define ff first
#define ss second
#define P 1000000007
#define in(x, a, b) (a <= x && x < b)

using namespace std;
using ll = long long;
typedef pair<int, int> ii;
typedef vector<ii> vii; 
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
const ll inf = 1000000001, INF = (ll)1e18 + 1;

const int maxn = 1e6 + 10;

int n, k = 0, h = 0;
vi pos, pre, t, sim;

void build(int v = 1) {
	if(k >= n) return;
	t[v] = pre[k++];
	
	if(h < n && t[v] == pos[h]) {
		h++;
		return;
	}
	
	build(2 * v);
	build(2 * v + 1);
	h++;
}

void simme(int v = 1) {
	if(t[v] == -1) return;
	simme(v * 2);
	sim.pub(t[v]);
	simme(v * 2 + 1);
}

void visita(int N, int *PRE, int *POST, int *SIMM) {
	n = N;
	pos.resize(n), pre.resize(n);
	for(int i = 0; i < n; i++) pre[i] = PRE[i];
	for(int i = 0; i < n; i++) pos[i] = POST[i];
	
	t.resize(4 * maxn, -1);
	build();
	
	simme();
	assert(sim.size() == n);
	for(int i = 0; i < sim.size(); i++) SIMM[i] = sim[i];
}

Riguardo l’implementazione non ho molto da dire, ho visto un pattern e scritto il codice (definiamola constructive :sweat_smile:).

2

Dando un’occhiata veloce al tuo codice mi sembra di capire che cerchi di memorizzare un albero in un array di grandezza 4N dove t[2*i] e t[2*i+1] sono i figli sinistro e destro di t[i], ma questa implementazione non funziona se l’albero ha un’altezza maggiore di log(N). Nell’esercizio in questione non ci sono limitazioni sull’altezza dell’albero.

1 Mi Piace