Problemi con Time out

Algoritmi
1

Buongiorno, vi volevo chiedere un aiuto, ho ancora un paio di problemi non risolti completamente per via del dell’errore di time out, perciò vorrei chiedervi se mi potreste consigliere degli algoritmi o delle funzioni della STL che sono utili per velocizzare il tempo di esecuzione, anche algoritmi che sfruttano gli alberi perché ho ancora il problema “Alberi” da completare (sempre per time out) e mi piacerebbe liberarmi di questi problemi una volta per tutte!

1 Mi Piace
2

Salve, a seconda del compito del svolgere potrebbero esserci delle funzioni nella std che potrebbero aiutarti. Indicare banalmente algoritmi su alberi è piuttosto ambiguo :sweat_smile:
Per quanto riguarda il tuo problema su alberi prova a esporre il tuo ragionamento, postare banalmente il codice non aiuta chi vorrebbe aiutarti :stuck_out_tongue_closed_eyes:

3

ah ok in effetti hai completamente ragione, questo è il codice di alberi, la mia idea è la seguente:
Data la visita pre e post order sappiamo per certo che il primo numero contenuto nel vettore con la vista pre-order è il nodo che rappresenta la radice(perdonatevi i termini non proprio esatti), dopo di che semplicemente scorro tutto il vettore con la visita pre-order e inserisco mano mano ogni nodo seguendo il seguente ragionamento:

  • Parto a inserire ogni nodo controllando dalla radice;
  • Prima di tutto controllo se l’attuale nodo analizzato è vuoto e in quel caso aggiungo nel “valore” del nodo, il numero che sto attualmente inserendo;
  • Nel caso in nodo non sia vuoto cerco, il valore a cui devo trovare un nodo vuoto per andarlo a inserire, nel vettore contente la visita post-order e faccio lo stesso con il valore del nodo su cui mi trovo attualmente (il valore è contenuto nel campo dello struct info) e l’indice in cui è stato trovato il nodo attuale è maggiore dell’indice in cui è stato trovato il valore del nodo da inserire nel vettore con la visita pre-order richiamo la funzione d’inserimento ricorsivamente sostituendo il parametro “padre” con il nodo che sto visitando attualmente e il nodo da visitare con il nodo sx del nodo attuale (perdonatemi se non si è capito molto bene ma sono una schiappa a parole ma spero che guardando la seguente riga di codice penso sia più comprensibile);
insert_tree(pos,p,p->sx,POS,N);
  • Ora tornando al controllo precedente( quello sull’ indici ) se la posizione del nodo attualmente visitato è minore del nodo che devo inserire allo richiamo ricorsivamente la funzione di inserimento sostituendo il parametro “padre” con il padre del nodo visitato attualmente e il parametro contenente il nodo da visitare lo sostituisco con il figlio destro del padre del nodo che sto visitando attualmente(penso che guardando la seguente riga di codice sia più comprensibile);
insert_tree(pos,p->parent,p->parent->dx,POS,N);

Questo è il codice completo.

#include <bits/stdc++.h>
#define MAXN 1000010
using namespace std;
struct nodo{
	int info;
	nodo* parent;
	nodo* sx;
	nodo* dx;
};
int N;
int pre[MAXN];
int post[MAXN];
int sim[MAXN];
int i=0;
void pre_order(nodo* p,int SIM[]){
	if(p!=NULL){
		pre_order(p->sx,SIM);
		//cout<<p->info<<" ";
		SIM[i]=p->info;
		i++;
		pre_order(p->dx,SIM);
	}
}
void insert_tree(int pos ,nodo* &padre ,nodo* &p ,int POS[] , int N){
	if(p==NULL){
		p=new nodo;
		p->info=pos;
		p->parent=padre;
		p->sx=NULL;
		p->dx=NULL;
		//cout<<p->info<<" : "<<p->parent->info<<endl;
	}
	else{
		auto it=find(POS,POS+N,pos);
		auto itn=find(POS,POS+N,p->info);
		if(it-POS<itn-POS){
			insert_tree(pos,p,p->sx,POS,N);
		}
		else{
			if(it-POS>itn-POS){
				insert_tree(pos,p->parent,p->parent->dx,POS,N);
			}
		}
	}
}
void visita(int N, int *PRE, int *POST, int *SIMM){
	nodo* root=new nodo;
	root->info=PRE[0];
	root->sx=NULL;
	root->dx=NULL;
	root->parent=NULL;
	for(int j=1;j<N;j++){
		insert_tree(PRE[j],root->parent,root,POST,N);
	}
	pre_order(root,SIMM);
	//cout<<endl;
}
int main(){
	cin>>N;
	for(int i=0;i<N;i++){
		cin>>pre[i];
	}
	for(int i=0;i<N;i++){
		cin>>post[i];
	}
	visita(N,pre,post,sim);
}