Problema Circus Show 10/100

Aiuto
1 
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int N;
vector <int> Adj(1000001);
vector <int> ReverseAdj[1000001];
vector <pair <int, int>> Qualcosa;
int Pos[1000001];
bool V[1000001];

void Reverse_DFS(int S) {
	
	if(V[S]) return;
	V[S] = 1;
	Qualcosa.push_back({S, 2});
	Pos[S] = 2;
	for(auto i : ReverseAdj[S]) Reverse_DFS(i);
}

int main() {
	
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> N;
	for(int i = 0; i < N; i++) {
		
		int a; cin >> a;
		
		Adj[i] = a;
		ReverseAdj[a].push_back(i);
	}
	
	int idx = 0;
	
	while(true) {
		
		if(V[idx]) break;
		V[idx] = 1;
		Qualcosa.push_back({idx, 1});
		Pos[idx] = 1;
		idx = Adj[idx];
	}
	
	if(Pos[N-1] == 1) {
		
		cout << 0;
		exit(0);
	}
	
	Reverse_DFS(N-1);
	
	sort(Qualcosa.begin(), Qualcosa.end());
	
	int Uno = -1, Due = -1;
	
	int Res = 99999999;
	
	for(int i = 0; i < Qualcosa.size(); i++) {
		
		if(Qualcosa[i].second == 1) Uno = Qualcosa[i].first;
		if(Qualcosa[i].second == 2) Due = Qualcosa[i].first;
		
		if(Uno != -1 && Due != -1) Res = min(Res, abs(Uno-Due));
	}
	
	cout << Res;
	
	//for(auto i : Qualcosa) cout << i.first << " " << i.second << "\n";
	
	// for(int i = 0; i < N; i++) cout << Pos[i] << " ";
}

Buonasera, stavo provando a risolvere il problema Circus Show e volevo avere un vostro parere del perché in alcuni casi l’output risulta sbagliato. L’idea si basa all’inizio di eseguire una semplice DFS partendo dal cannone 0 per controllare quali cannoni possono essere raggiunti (ed eventualmente spostati) e se è possibile raggiungere fin dall’inizio il cannone N-1. Nel caso in cui non è possibile raggiungere il cannone N-1 eseguo una DFS al “contrario” ovvero vado ad esplorare tutti i cannoni che possono portarti al canone S. Per fare un esempio nel secondo caso d’esempio con la funzione Reverse_DFS partendo dal cannone N-1 la funziona passerà immediatamente al cannone 2 poiché è possibile raggiungere il cannone N-1 passando proprio per il cannone 2. In entrambe le DFS mi salvo all’interno del vettore “Qualcosa” (non sapevo che nome dargli) tutti i cannoni che sono stati esplorati suddividendoli con un identificativo (1: tutti i cannoni raggiungibili partendo dal cannone 0; 2: tutti i cannoni che fanno parte del percorso per raggiungere il cannone N-1). Dopo di che ordino il vettore “Qualcosa” ed infine calcolo il risultato minore sottraendo il valore assoluto degli elementi 1 e 2 più vicini. Grazie e scusate per la lunga spiegazione.

2

L’ho risolto un anno fa e non ricordo bene ma mi sembra che la tua soluzione non sia sempre la migliore: non è detto che, trovato l’insieme dei cannoni a costo 0 dal primo cannone e l’insieme dei cannoni a costo 0 dall’ultimo cannone, la soluzione migliore sia trovare la distanza fra gli elementi più vicini dei due insiemi.
Sono partito dagli elementi del primo insieme trovando gli elementi a distanza 1 da questi fino a che …

3

Spero di aver capito. In pratica, oltre alle traiettorie che mi vengono date in input, aggiungo per ogni cannone delle traiettorie per i loro vicini con costo 1. Ovviamente quelli già presenti nel problema avranno peso 0 poiché il cannone è già posizionato in quella traiettoria, mentre invece quelle che aggiungo io hanno peso 1 poiché per spostarsi da un cannone ad uno i+1 o i-1 basta un’unità di tempo. Dopo di ché mi basta cercare semplicemente il percorso più breve partendo dal cannone 0 fino ad arrivare al cannone N-1. Correggimi se sbaglio.

4

Ho appena provato ad implementare l’idea che ho esposto precedentemente e mi ha dato 100/100. Grazie mille per l’aiuto.

5

Si direi che le idee sono queste: prima trovo l’insieme dei cannoni con costo 0 se qui non c’è il cannone N-1 trovo, a partire dagli elementi di questo insieme, l’insieme dei cannoni di costo 1 (che non sono solo quelli a distanza +1 o -1 da quelli di costo 0 che li hanno generati) se tra questi non c’è il cannone N-1 …
Le liste di adiacenza potrebbero non servire, non le ho usate.