Error en problema "erdos-darwin"

Problemas Nivel 3
#1

Estaba haciendo el problema “erdos-darwin” en oiajuez y me da resultado incorrecto en el último caso, creo que el error es por usar vectores demasiado grandes porque nunca había resuelto un problema que use vectores de hasta 100000x100000, acá está el código:

#include <iostream>
#include <vector>
#include <queue>
#include <unordered_set>
#include <algorithm>
using namespace std;

vector<int> BFS(vector<vector<int> > &lista , int nodoInicial) {
  int n = lista.size(), t;
  queue<int> cola;
  vector<int> distancias (n,n);
  cola.push(nodoInicial) ;
  distancias[nodoInicial] = 0;
  while(! cola.empty( )) {
      t = cola.front() ;
      cola.pop( ) ;
      for(int i =0;i<lista [ t ]. size ( ) ; i++){
         if (distancias[ lista [ t ][ i ]]==n) {
            distancias[ lista [ t ][ i ]] = distancias[ t]+1;
            cola.push( lista [ t ][ i ] ) ;
         }
      }
   }
 return distancias;
}   


int main(){
    ios_base::sync_with_stdio(false); 
    int N, M, d, a, b,sum=0;
    sum=0;
    
    vector <int> erdos;
    vector <int> darwin;

    cin>>N>>M;
    vector <vector<int>> grafo(N);

    cin>>d;
    for(int i=0;i<M;i++){
        cin>>a>>b;
        grafo[a-1].push_back(b-1);
        grafo[b-1].push_back(a-1);
    }
    
    erdos=BFS(grafo,0);

    darwin=BFS(grafo,N-1);

    for(int i=0;i<erdos.size();i++){
        if((erdos[i]+darwin[i])<=d){
            sum++;
            
        }
    }
    cout<<sum;

}
1 me gusta
#2

¡Hola!

Fijate que si bien el vector<vector<int> > que estás usando es bidimiensional, no todas las listas de vecinos de cada nodo tienen por qué estar completas. De hecho, como al leer el grafo por cada arista se están sumando exactamente 2 elementos (uno a la lista correspondiente a cada extremo), en total la suma de los largos de las listas será de 2M elementos. Por lo tanto no creo que esté allí el problema.

Sospecho que lo que está pasando en este problema es en casos donde un nodo no se conecta con alguno de los dos científicos y el valor de d sea bien grande, para fijar conceptos supongamos d = 2N. En un caso donde alguien no se conecta con alguno de ellos no debería sumar uno al contador en la respuesta. Sin embargo, como el arreglo distancias se inicializa con n, en el caso en que d = 2N se estarían considerando a todos los colaboradores en la respuesta, independientemente de si están conectados o no…

Si algo no quedó claro de lo que está pasando, o si no queda claro cómo modificar el algoritmo para tener esto en cuenta no dudes en escribir de nuevo :slight_smile:

2 Me gusta