Submission #1138045

#	Time	Username	Problem	Language	Result	Execution time	Memory
1138045		Gabriel	Crocodile's Underground City (IOI11_crocodile)	C++20	0 / 100	0 ms	320 KiB

crocodile

#include "crocodile.h"
#include "bits/stdc++.h"
using namespace std;
struct Arista{
  long long Nodo, Peso;
};
struct Arista_completa{
  long long a, b, Peso;
};
struct Nodo_por_ver{
  long long Distancia, Nodo, Padre;
};
bool operator<(const Arista &a, const Arista &b){
  if(a.Peso < b.Peso) return 1;
  if(a.Peso > b.Peso) return 0;
  return a.Nodo < b.Nodo;
}
bool operator<(const Arista_completa &a, const Arista_completa &b){
  if(a.Peso < b.Peso) return 1;
  if(a.Peso > b.Peso) return 0;
  if(a.a < b.a) return 1;
  if(a.a > b.a) return 0;
  return a.b < b.b;
}
bool operator<(const Nodo_por_ver &a, const Nodo_por_ver &b){
  if(a.Distancia < b.Distancia) return 1;
  if(a.Distancia > b.Distancia) return 0;
  if(a.Nodo < b.Nodo) return 1;
  if(a.Nodo > b.Nodo) return 0;
  return a.Padre < b.Padre;
}
multiset<Arista_completa> Lista_de_aristas;
vector< vector<Arista> > Grafo;
vector<bool> Salidas;
vector<long long> Veloz(long long n){
  vector<long long> Padres(n, -2), Distancias(n, 2222222222222222);
  set<Nodo_por_ver> Cola;
  Nodo_por_ver Inicio;
  Inicio.Distancia = 0;
  Inicio.Nodo = 0;
  Inicio.Padre = 0;
  Cola.insert(Inicio);
  while(!Cola.empty()){
    Nodo_por_ver Actual = *Cola.begin();
    Cola.erase(Cola.begin());
    if(Distancias[Actual.Nodo] > Actual.Distancia){
      Distancias[Actual.Nodo] = Actual.Distancia;
      Padres[Actual.Nodo] = Actual.Padre;
    } else continue;
    for(auto E: Grafo[Actual.Nodo]){
      if(Distancias[E.Nodo] > Distancias[Actual.Nodo] + E.Peso){
        //Distancias[E.Nodo] = Distancias[Actual.Nodo] + E.Peso;
        Nodo_por_ver Siguiente;
        Siguiente.Nodo = E.Nodo;
        Siguiente.Distancia = Distancias[Actual.Nodo] + E.Peso;
        Siguiente.Padre = Actual.Nodo;
        Cola.insert(Siguiente);
      }
    }
  }
  for(long long i = 0; i < n; i++){
    cout<<Distancias[i]<<" ";
  }
  return Padres;
}
long long Obtener_distancia(long long n){
  vector<long long> Padres(n, -2), Distancias(n, 2222222222222222);
  set<Nodo_por_ver> Cola;
  Nodo_por_ver Inicio;
  Inicio.Distancia = 0;
  Inicio.Nodo = 0;
  Inicio.Padre = 0;
  long long Menor = 2222222222222222;
  Cola.insert(Inicio);
  while(!Cola.empty()){
    Nodo_por_ver Actual = *Cola.begin();
    Cola.erase(Cola.begin());
    if(Distancias[Actual.Nodo] > Actual.Distancia){
      Distancias[Actual.Nodo] = Actual.Distancia;
      Padres[Actual.Nodo] = Actual.Padre;
    } else continue;
    for(auto E: Grafo[Actual.Nodo]){
      if(Distancias[E.Nodo] > Distancias[Actual.Nodo] + E.Peso){
        //Distancias[E.Nodo] = Distancias[Actual.Nodo] + E.Peso;
        Nodo_por_ver Siguiente;
        Siguiente.Nodo = E.Nodo;
        Siguiente.Distancia = Distancias[Actual.Nodo] + E.Peso;
        Siguiente.Padre = Actual.Nodo;
        Cola.insert(Siguiente);
      }
    }
  }
  for(long long i = 0; i < n; i++) if(Salidas[i]) Menor = min(Menor, Distancias[i]);
  return Menor;
}
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]){
  long long n = N, m = M;
  Grafo.assign(n, {});
  Salidas.assign(n, 0);
  for(long long i = 0; i < m; i++){
    Arista a, b;
    a.Nodo = R[i][0];
    b.Nodo = R[i][1];
    a.Peso = L[i];
    b.Peso = a.Peso;
    Arista_completa _1;
    _1.a = a.Nodo;
    _1.b = b.Nodo;
    _1.Peso = a.Peso;
    Lista_de_aristas.insert(_1);
    swap(_1.a, _1.b);
    Lista_de_aristas.insert(_1);
    Grafo[a.Nodo].push_back(b);
    Grafo[b.Nodo].push_back(a);
  }
  /*for(long long i = 0; i < K; i++) Salidas[P[i]] = 1;
  vector<long long> Padres = Veloz(n);
  Grafo.assign(n, {});
  for(long long i = 0; i < n; i++){
    Arista_completa _1;
    _1.a = i;
    _1.b = Padres[i];
    _1.Peso = -2;
    Arista a, b;
    a.Nodo = i;
    b.Nodo = Padres[i];
    a.Peso = (*Lista_de_aristas.lower_bound(_1)).Peso;
    b.Peso = a.Peso;
    Grafo[a.Nodo].push_back(b);
    Grafo[b.Nodo].push_back(a);*/
    /*Arista_completa a;
    a.a = i;
    a.b = Padres[i];
    a.Peso = -2;
    a.Peso = (*Lista_de_aristas.lower_bound(a)).Peso;
    Lista_de_aristas.erase(a);
    swap(a.a, a.b);
    Lista_de_aristas.erase(a);*/
  //}
  vector<long long> Distancias(n, 2222222222222222);
  deque<long long> Cola = {0};
  Distancias[0] = 0;
  int r = 0;
  while(!Cola.empty()){
    long long Nodo = Cola[0];
    Cola.pop_front();
    for(auto E: Grafo[Nodo]){
      if(Distancias[E.Nodo] > Distancias[Nodo] + E.Peso){
        Distancias[E.Nodo] = Distancias[Nodo] + E.Peso;
        r = max(r, (int)(Distancias[Nodo] + E.Peso));
        Cola.push_back(E.Nodo);
      }
    }
  }
  /*for(auto E: Lista_de_aristas){
    Arista a, b;
    a.Nodo = E.a;
    b.Nodo = E.b;
    a.Peso = E.Peso;
    b.Peso = E.Peso;
    Grafo[a.Nodo].push_back(b);
    Grafo[b.Nodo].push_back(a);
  }*/
  return r;
}

• Subtask 1: 0 / 46
• Subtask 2: 0 / 43
• Subtask 3: 0 / 11