Stavo provando a risolvere vasi2 e per farlo ho creato una versione modificata di uno scapegoat tree che secondo i miei calcoli dovrebbe avere come complessità di ricerca e inserimento O(log(n)) (che dovrebbe essere proprio quella richiesta). Purtroppo però il programma va in tle in alcuni testcase, e in particolare in quelli dell’ultimo subtask addirittura sfora il limite di memoria (mentre quelli che risolve sono corretti). Quello che non capisco è perchè solamente inviando un programma semplice con la sola funzione build per costruire l’albero va comunque in TLE. Ho provato anche a fare dei test col mio portatile (che non è molto potente) e queste sono alcune cose che non mi tornano:
- Per costruire un albero con 10^6 nodi il mio portatile ci mette circa 1 decimo di secondo, mentre il correttore 8
- Nel caso i nodi siano 10^7 il correttore da errore perchè viene usata tutta la memoria disponibile. Mi sembra abbastanza strana come cosa perchè sul mio computer non da problemi e 512 MiB per conservare 10 milioni di nodi mi sembrano un po’ troppi
Dato che è la prima volta che provo a implementare strutture dati del genere, riuscireste ad aiutarmi almeno a capire perchè questo programma gira così lentamente?
Ecco il codice che contiene solo la funzione build:
#include <iostream>
using namespace std;
class ScapegoatTree
{
/*
per ogni nodo salvo il suo valore, il numero di nodi
nel suo sottoalbero e i puntatori per il figlio destro e sinistro
*/
struct node
{
int val, card;
node *l = NULL, *r = NULL;
};
node *root; // radice dell'albero
int dim; // numero di nodi
/*
con la funzione construsci creo un albero binario
perfettamente bilanciato. La ricorsione si ferma
quando viene creato un nodo 'fittizio' che in teoria
non dovrebbe esistere, in pratica mi serve per
semplificare altre procedure
*/
void costruisci(node *v, int tl, int tr)
{
int tm = (tl + tr) / 2;
v->val = tm;
v->card = tr - tl + 1;
if (v->card == 0)
return;
v->l = new node;
costruisci(v->l, tl, tm-1);
v->r = new node;
costruisci(v->r, tm+1, tr);
}
public:
// creazione della radice e costruzione dell'albero
void build(int n)
{
root = new node;
dim = n;
costruisci(root, 0, dim-1);
}
};
int N;
ScapegoatTree albero;
int main()
{
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
cin >> N;
albero.build(N);
return 0;
}