Ciao, stavo provando a risolvere parkour. Ho pensato di cercare il peso più alto che trovo nel percorso più leggero, in un grafo diretto in cui il peso di un edge è dato dall’altezza della casa destinazione e ogni nodo è una casa i.
Ho quindi salvato i 3 vector in input in questo modo:
int salta(int n, vector<int> s, vector<int> a, vector<int> b){
s.push_back(0); // così se da una casa puoi arrivare al parco, il peso (altezza) del parco è 0 essendo messo all'ultima pos
vector<pair<int, pair<int, int>>> edges; // {peso (altezza end), {start, end}}
for(int i = 0; i < n; i++)
for(int j = a[i]; j <= b[i]; j++)
edges.push_back({s[i+j], {i, i+j}});
in questo modo, il primo testcase ci crea una edge list fatta così:
1 -> 4 con peso(0)
3 -> 4 con peso(0)
0 -> 2 con peso(1)
0 -> 3 con peso(2)
2 -> 3 con peso(2)
0 -> 1 con peso(3)
ora ordino la edge list in ordine crescente in base al peso di ogni edge usando sort(edges.begin(), edges.end()); e uso la binary search per cercare la lista di edge che formano un percorso con meno peso possibile e controllo che il percorso sia valido utilizzando la DFS.
Classe Graph:
class Graph {
private:
int nodes;
vector<vector<int>> graph;
public:
Graph(int n) {
nodes = n;
graph.resize(n);
}
void addEdge(pair<int, int> edge) {
graph[edge.first].push_back(edge.second);
}
bool path(int x, int y) {
if(x == y) return true;
bool visited[nodes] = {false};
stack<int> s;
s.push(x);
visited[x] = true;
while(!s.empty()) {
x = s.top();
s.pop();
for(int i = 0; i < graph[x].size(); i++) {
if(graph[x][i] == y) return true;
if(!visited[graph[x][i]]) {
s.push(graph[x][i]);
visited[graph[x][i]] = true;
}
}
}
return false;
}
void print() {
for(int i = 0; i < graph.size(); i++)
for(int j = 0; j < graph[i].size(); j++)
cout<<i<<" -> "<<graph[i][j]<<endl;
cout<<endl;
}
};
Binary search con DFS e return:
int low = -1;
int high = edges.size()-1;
int mid;
// binary search
while(high - low > 1) {
mid = low + (high - low) / 2;
Graph g(n+1); // +1 perché c'è il nodo finale aggiunto all'inizio che rappresenta il parco
for(int i = 0; i <= mid; i++) // aggiungo tutti gli edge da 0 a mid
g.addEdge(edges[i].second);
// se il percorso è valido, quindi se si può raggiungere il parco
if(g.path(0, n)) high = mid;
else low = mid;
}
return edges[high].first; // ritorno il peso dell'edge con peso maggiore utilizzato
L’ho provato su carta e funziona sempre ma quando lo provo sul cms fa 0/100 dandomi alcuni risultati corretti, altri sbagliati, e dalla subtask 4 in poi altri con memoria max e 1 con limite di tempo. Non ho proprio idea di cosa potrebbe non andare ahaha.
Il codice completo che ho mandato:
#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
class Graph {
private:
int nodes;
vector<vector<int>> graph;
public:
Graph(int n) {
nodes = n;
graph.resize(n);
}
void addEdge(pair<int, int> edge) {
graph[edge.first].push_back(edge.second);
}
bool path(int x, int y) {
if(x == y) return true;
bool visited[nodes] = {false};
stack<int> s;
s.push(x);
visited[x] = true;
while(!s.empty()) {
x = s.top();
s.pop();
for(int i = 0; i < graph[x].size(); i++) {
if(graph[x][i] == y) return true;
if(!visited[graph[x][i]]) {
s.push(graph[x][i]);
visited[graph[x][i]] = true;
}
}
}
return false;
}
};
int salta(int n, vector<int> s, vector<int> a, vector<int> b){
s.push_back(0);
vector<pair<int, pair<int, int>>> edges; // {peso (altezza end), {start, end}}
for(int i = 0; i < n; i++)
for(int j = a[i]; j <= b[i]; j++)
edges.push_back({s[i+j], {i, i+j}});
sort(edges.begin(), edges.end());
int low = -1;
int high = edges.size()-1;
int mid;
while(high - low > 1) {
mid = low + (high - low) / 2;
Graph g(n+1);
for(int i = 0; i <= mid; i++)
g.addEdge(edges[i].second);
if(g.path(0, n)) high = mid;
else low = mid;
}
return edges[high].first;
}
.