Submission #1209211

#	Time	Username	Problem	Language	Result	Execution time	Memory
1209211		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 , long long>>> g(N);
   for(int i = 0;i < M;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<long long>> dist(N , vector<long long>(2 , -1));
   priority_queue<pair<long long , int> , vector<pair<long long , int>> , greater<pair<long long , int>>> pq;
   for(int i = 0;i < K;i ++){
      for(int w = 0;w < 2;w ++){
         dist[P[i]][w] = 0;
      }
      pq.push(pair<long long , int>{0LL , P[i]});
   }
   while((int)pq.size()){
      auto [d , u] = pq.top();
      pq.pop();
      if(dist[u][1] != d){
         continue;
      }
      for(auto [v , w] : g[u]){
         d += w;
         long long a = dist[v][1];
         for(int q = 0;q < 2;q ++){
            if(dist[v][q] == -1 || dist[v][q] > a){
               if(q == 0){
                  swap(dist[v][0] , dist[v][1]);
               }
               dist[v][q] = a;
               break;
            }
         }
         if(dist[v][1] != a){
            pq.push(pair<long long , int>{dist[v][1] , v});
         }
         d -= w;
      }
   }
   return dist[0][1];
}

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