Submission #1138064

#	Time	Username	Problem	Language	Result	Execution time	Memory
1138064		Gabriel	Crocodile's Underground City (IOI11_crocodile)	C++20	89 / 100	2105 ms	215820 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;
  //long long 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;*/
  return a.Nodo < b.Nodo;
}
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]){
  long long n = N, m = M;
  multiset<Arista_completa> Lista_de_aristas;
  vector< vector<Arista> > Grafo(n);
  //vector<bool> Salidas(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< multiset<long long> > Distancias(n);
  multiset<Nodo_por_ver> Cola;
  for(long long i = 0; i < K; i++){
    Distancias[P[i]].insert(0);
    Nodo_por_ver a;
    a.Nodo = P[i];
    a.Distancia = 0;
    //a.Padre = P[i];
    Cola.insert(a);
  }
  while(!Cola.empty()){
    Nodo_por_ver Actual = *Cola.begin();
    //cout<<Actual.Nodo<<" "<<Actual.Distancia<<"\n";
    Cola.erase(Cola.begin());
    bool Sirve = 0;
    if(Distancias[Actual.Nodo].size() <= 1){
      Distancias[Actual.Nodo].insert(Actual.Distancia);
      if(Distancias[Actual.Nodo].size() == 2) Sirve = 1;
    } else {
      Distancias[Actual.Nodo].insert(Actual.Distancia);
      auto E = Distancias[Actual.Nodo].end();
      E--;
      if(*E != Actual.Distancia){
        Sirve = 1;
      }
      Distancias[Actual.Nodo].erase(E);
    }
    if(Actual.Nodo == 0) Sirve = 0;
    if(!Sirve) continue;
    auto e = Distancias[Actual.Nodo].end();
    e--;
    Actual.Distancia = *e;
    for(auto E: Grafo[Actual.Nodo]){
      Nodo_por_ver Siguiente;
      Siguiente.Distancia = E.Peso + Actual.Distancia;
      Siguiente.Nodo = E.Nodo;
      Cola.insert(Siguiente);
    }
  }
  /*for(auto E: Distancias){
    cout<<*E.begin()<<" ";
  }*/
  auto E = Distancias[0].end();
  E--;
  return (int)(*E);
}

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