Stavo provando a risolvere incendio e ho trovato una soluzione in M^2, che però non funziona. Sostanzialmente la mia idea è questa: divido il perimetro della griglia in 2, una metà composta dal lato superiore e a destra, un’altra metà composta dal lato inferiore e a sinistra. Se c’è una zona “a fuoco” continua (per continua intendo che tra due caselle esiste sempre un percorso che va da una all’altra facendo anche “mosse” in diagonale) che va dalla parte del perimetro in alto a destra a quella in basso a sinistra allora non è più possibile andare da (0,0) a (N-1, N-1).
Per far questo in M^2 identifico 2 tipi di eventi fondamentali:
- una “macchia” di fuoco tocca una delle due parti in cui abbiamo diviso il perimetro che prima non toccava
- due “macchie” si fondono
Prima di tutto calcolo tutti gli eventi possibili in O(2M + M^2), poi uso una DSU per sapere quanto dista una macchia di fuoco da ciascuna delle 2 parti in cui ho diviso il perimetro man mano che “fondo” le macchie.
Questa idea dovrebbe funzionare - nei miei test è abbondantemente sotto il TL anche se non ho ottimizzato la DSU - ma per qualche motivo si bugga. Nello specifico in alcuni casi calcola tutti gli eventi senza che succeda niente (triggerando l’assert(false)) e in altri mi da semplicemente risposta sbagliata. Sospetto che ci sia qualche problema con la funzione che calcola dopo quanto tempo due “macchie” entrano a contatto, ma anche dopo aver provato diverse versioni nulla ha funzionato. Avete idea di cosa potrebbe essere “rotto”? Grazie mille!!!
#include<bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define pb push_back
#define rb pop_back
typedef long long ll;
typedef long long unsigned llu;
typedef ll num;
const num oo = numeric_limits<num>::max();
typedef pair<int, int> ii;
typedef vector<num> vi;
typedef vector<vi> mi;
#define deb(x) cerr << __LINE__ << ": " << #x << " = " << (x) << endl
struct fire{
ii pos;
ll dist_1;
ll dist_2;
int parent;
int id;
fire(ii POS, int N, int ID){
pos = POS;
dist_1 = min(POS.f, N-1-POS.s); dist_2 = min(N-1-POS.f, POS.s);
parent = ID; id = ID;
}
fire(){};
};
vector<fire> INFERNO;
fire get_repr(fire F){
while(F.parent != F.id){
F = INFERNO[F.parent];
}
return F;
}
void join(fire &a, fire &b){
a = get_repr(a);
b = get_repr(b);
if(a.id == b.id) return;
b.parent = a.id;
a.dist_1 = min(a.dist_1, b.dist_1);
a.dist_2 = min(a.dist_2, b.dist_2);
INFERNO[a.id] = a;
INFERNO[b.id] = b;
}
int alzati(int N, int M, int X[], int Y[]) {
INFERNO.clear();
INFERNO.resize(M);
for(int i=0; i<M; i++){
INFERNO[i] = fire({X[i], Y[i]}, N, i);
}
// {{istante in cui avviene, tipo di evento}, {casella1, casella2}}
// se il tipo di evento è 0 una macchia di fuoco tocca un lato, se è 1 due macchie di fuoco si fondono
vector<pair<ii, ii>> events;
for(int i=0; i<M; i++){
events.push_back({{INFERNO[i].dist_1, 0}, {i, i}});
events.push_back({{INFERNO[i].dist_2, 0}, {i, i}});
for(int j=i+1; j<M; j++){
ll dist;
if(INFERNO[i].pos.f == INFERNO[j].pos.f or INFERNO[i].pos.s == INFERNO[j].pos.s){
dist = (abs(INFERNO[i].pos.f - INFERNO[j].pos.f) + abs(INFERNO[i].pos.s - INFERNO[j].pos.s))/2;
}else{
dist = (abs(INFERNO[i].pos.f - INFERNO[j].pos.f) + abs(INFERNO[i].pos.s - INFERNO[j].pos.s)-1)/2;
}
events.push_back({{dist, 1}, {i, j}});
}
}
sort(events.begin(), events.end());
for(auto e: events){
if(e.f.s == 0){
fire repr = get_repr(INFERNO[e.s.f]);
if(repr.dist_1 <= e.f.f and repr.dist_2 <= e.f.f) return e.f.f-1;
}else{
join(INFERNO[e.s.f], INFERNO[e.s.s]);
fire repr = get_repr(INFERNO[e.s.f]);
if(repr.dist_1 <= e.f.f and repr.dist_2 <= e.f.f) return e.f.f-1;
}
}
assert(false);
}