Submission #778240

#	Time	Username	Problem	Language	Result	Execution time	Memory
778240		a_aguilo	Crocodile's Underground City (IOI11_crocodile)	C++14	100 / 100	561 ms	67632 KiB

crocodile

#include "crocodile.h"
#include<bits/stdc++.h>

using namespace std;

int n, m, k;
const int maxN = 100000;
vector<pair<int, int>> AdjList[maxN];
int isExit[maxN];
int bestPlan[maxN][2];
int secondBest[maxN][2];
int dist[maxN];

void dijkstra(){
  priority_queue<vector<int>> PQ;
  for(int i = 0; i < n; ++i){
    if(isExit[i]){
      bestPlan[i][0] = secondBest[i][0] = 0;
      bestPlan[i][1] = secondBest[i][1] = -1;
      PQ.push({0, i, -1});
    }
    else{
      bestPlan[i][0] = secondBest[i][0] = 1e9;
      bestPlan[i][1] = secondBest[i][1] = -1;
    }
  }
  //{-dist, nodo, padre};
  while(!PQ.empty()){
    vector<int> act = PQ.top(); PQ.pop();
    int dist = -act[0];
    int node = act[1];
    int padre = act[2];
    if(padre == secondBest[node][1] && dist == secondBest[node][0]){
      //cout << node << " " << dist << endl;
      for(pair<int, int> next: AdjList[node]){
        int vecino = next.first;
        int d = next.second + dist;
        if(d < bestPlan[vecino][0]){
          if(bestPlan[vecino][1] != -1){
            secondBest[vecino][0] = bestPlan[vecino][0];
            secondBest[vecino][1] = bestPlan[vecino][1];
            bestPlan[vecino][0] = d;
            bestPlan[vecino][1] = node;
            PQ.push({-secondBest[vecino][0], vecino, secondBest[vecino][1]});
          }else{
            bestPlan[vecino][0] = d;
            bestPlan[vecino][1] = node;
          }
        }else if(d < secondBest[vecino][0]){
          secondBest[vecino][0] = d;
          secondBest[vecino][1] = node;
          PQ.push({-d, vecino, node});
        }
      }
    }
  }
}


int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]){
  n = N;
  m = M;
  k = K;
  int a, b, w;
  for(int i = 0; i < M; ++i){
    a = R[i][0];
    b = R[i][1];
    w = L[i];
    AdjList[a].push_back({b, w});
    AdjList[b].push_back({a, w});
  }
  memset(isExit, 0, sizeof(isExit));
  for(int i = 0; i < k;++i) isExit[P[i]] = 1;
  dijkstra();
  return secondBest[0][0];
}

/*
int main(){
  int N, M, K;
  cin >> N >> M >> K;
  int R[M][2];
  int L[M];
  int P[K];
  for(int i = 0; i < M; ++i) cin >> R[i][0] >> R[i][1] >> L[i];
  for(int i = 0; i < K; ++i) cin >> P[i];
  cout << travel_plan(N, M, R, L, K, P);
  return 0;
}

*/

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