Submission #1209135

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

crocodile

#include<bits/stdc++.h>
#include "crocodile.h"
using namespace std;

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]){
   vector<vector<pair<int , int>>> g(N);
   for(int i = 0;i < N;i ++){
      g[R[i][0]].emplace_back(R[i][1] , L[i]);
      g[R[i][1]].emplace_back(R[i][0] , L[i]);
   }
   vector<vector<int>> dist(N , vector<int>(2 , -1));
   priority_queue<pair<int , long long> , vector<pair<int , long long>> , greater<pair<int , long long>>> pq;
   for(int i = 0;i < K;i ++){
      for(int w = 0;w < 2;w ++){
         dist[P[i]][w] = 0;
      }
      pq.push(pair<int , long long>{P[i] , 0LL});
   }
   while((int)pq.size()){
      auto [u , d] = pq.top();
      pq.pop();
      if(dist[u][1] != d){
         continue;
      }
      for(auto [v , w] : g[u]){
         d += w;
         if(dist[v][0] == -1){
            dist[v][0] = d;
         }else if(dist[v][1] == -1){
            dist[v][1] = d;
            pq.push(pair<int , long long>{v , d});
         }else{
            if(d < dist[v][0]){
               swap(dist[v][0] , dist[v][1]);
               dist[v][0] = d;
               pq.push(pair<int , long long>{v , dist[v][1]});
            }else if(d < dist[v][1]){
               dist[v][1] = d;
               pq.push(pair<int , long long>{v , d});
            }
         }
         d -= w;
      }
   }
   return dist[0][0];
}

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