Ciao a tutti, stavo implementando la soluzione di Attenti all’incendio (incendio) con l’aiuto dell’editorial.
Per ora ho impostato la widest path con dijkstra e funziona sennonché va in TLE perché sto usando la coda di priorità quando in realtà non dovrei (lo dice della soluzione).
Qualcuno ha qualche indizio?
Questo è il codice:
#include <bits/stdc++.h>
using namespace std;
#define inf 1e9 + 5
using ii = pair<int, int>;
int n = 0, m = 0;
struct Node {
int x, y;
Node(int _x, int _y) : x(_x), y(_y) {}
int dist(Node a) { // calcola la distanza da un nodo all'altro
int dx = abs(x - a.x), dy = abs(y - a.y), t = (dx == 0 || dy == 0) - 1;
return (dx + dy + t) / 2;
}
int min_left_bottom() { // restituisce il minimo tra la distanza dal bordo sinistro
// e la distanza dal bordo sotto
return min(n - x - 1, y);
}
int min_top_right() {
return min(x, n - y - 1);
}
};
int alzati(int N, int M, int X[], int Y[]) {
n = N; m = M;
vector<Node> nodes;
for(int i = 0; i < M; ++i)
nodes.emplace_back(X[i], Y[i]);
// dijkstra variante: minimizzo il peso massimo di un arco in un cammino da
// - bordo sinisto a bordo sopra/destro
// - bordo sotto a bordo sopra/destro
vector<int> dist(M, inf);
priority_queue<ii> pq;
for(int i = 0; i < M; ++i) { // multiple source
dist[i] = nodes[i].min_left_bottom();
pq.emplace(dist[i], i);
}
while(pq.size()) {
int curr = pq.top().second;
pq.pop();
for(int next = 0; next < M; ++next) {
if(next == curr) continue;
int w = nodes[curr].dist(nodes[next]);
int d = max(dist[curr], w);
if(d < dist[next]) {
dist[next] = d;
pq.emplace(d, next);
}
}
}
int ans = INT_MAX;
for(int i = 0; i < M; ++i) {
ans = min(max(dist[i], nodes[i].min_top_right()), ans);
}
return ans - 1;
}
Fare Dijkstra senza priority queue, letteralmente; vediamo perché.
Questo grafo è completo, pertanto |E|=\mathcal{O}(|V|^2). La complessità di Dijkstra con la priority queue è \mathcal{O}((|E|+|V|)\log |V|)=\mathcal{O}(|V|^2\log |V|).
Ora analizziamo cosa succede se al posto di usare una priority queue cerchi il minimo scorrendo tutti gli elementi.
Per ogni arco aggiorni al massimo una distanza nell’array delle distanze, dunque tutti gli aggiornamenti delle distanze sono \mathcal{O}(|E|)=\mathcal{O}(|V|^2). Invece una singola ricerca del minimo richiede \mathcal{O}(|V|), e questa va effettuata al più |V| volte (infatti se hai visitato tutti i nodi l’algoritmo termina, e con la ricerca lineare puoi garantire di trovare sempre un nuovo nodo a meno che tutti i nodi raggiungibili siano già stati visitati).
Allora anche questa parte, e quindi tutto l’algoritmo, sono \mathcal{O}(|V|^2), che risulta essere un miglioramento rispetto alla complessità ottenuta con la priority queue.
Questo genere di ottimizzazione è abbastanza comune quando devi lavorare con grafi densi.
Piccola aggiunta. L’implementazione migliore attualmente conosciuta di Dijkstra usa come priority queue un Fibonacci heap al posto di un binary heap (che è la std::priority_queue). Poiché l’inserzione in un Fibonacci heap ha complessità ammortizzata costante, questo riduce a \mathcal{O}(|E|+|V|\log |V|) la complessità. I Fibonacci heap sono una rottura da scrivere e hanno un fattore costante altissimo quindi in pratica non servono mai, però se vuoi fare un tentativo una struttura equivalente dovrebbe essere implementata nelle pbds.
Le pbds sono una libreria non standard fornita da gcc, tuttavia è utilizzabile in praticamente ogni competizione.
Grazie mille, ho fatto 100/100 togliendo la priority queue e scorrendo tutti i nodi.
Per il fibonacci heap è uno buono spunto di approfondimento! Anche se penso, e spero, non sia poi necessario ai nazionali.