Submission #1209183

#	Time	Username	Problem	Language	Result	Execution time	Memory
1209183		pera	악어의 지하 도시 (IOI11_crocodile)	C++20	89 / 100	337 ms	48784 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 < 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<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>{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;
         if(dist[v][0] == -1){
            dist[v][0] = d;
         }else if(dist[v][1] == -1){
            dist[v][1] = d;
            if(dist[v][1] < dist[v][0]){
               swap(dist[v][1] , dist[v][0]);
            }
            pq.push(pair<int , long long>{dist[v][1] , v});
         }else{
            if(d < dist[v][0]){
               swap(dist[v][0] , dist[v][1]);
               dist[v][0] = d;
               pq.push(pair<int , long long>{dist[v][1] , v});
            }else if(d < dist[v][1]){
               dist[v][1] = d;
               pq.push(pair<int , long long>{d , v});
            }
         }
         d -= w;
      }
   }
   return dist[0][1];
}

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