제출 #1183873

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1183873		loom	Swapping Cities (APIO20_swap)	C++20	6 / 100	59 ms	11436 KiB

swap

#include "swap.h"
#include<bits/stdc++.h>
using namespace std;
#define inf 2e9

const int N = 1e5;
vector<pair<int,int>> g[N];
int mx;

void init(int n, int m, vector<int> u, vector<int> v, vector<int> w){
   for(int i=0; i<m; i++){
      g[u[i]].push_back({v[i], w[i]});
      g[v[i]].push_back({u[i], w[i]});
      mx = max(mx, w[i]);
   }

   for(int i=0; i<n; i++) if(g[i].size() == 1) mx = inf;
}

pair<vector<int>, vector<int>> dijkstra(int s, pair<int,int> pr = {-1, -1}){
   priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
   vector<int> dist(N, inf);
   pq.push({0, s});
   dist[s] = 0;
   vector<int> p(N);

   while(!pq.empty()){
      auto [d, v] = pq.top();
      pq.pop();
      if(d > dist[v]) continue;

      for(auto [ch, w] : g[v]){
         if(make_pair(v, ch) == pr or make_pair(ch, v) == pr) continue;

         int nw = max(d, w);
         if(nw < dist[ch]){
            dist[ch] = nw;
            p[ch] = v;
            pq.push({dist[ch], ch});
         }
      }
   }

   return {dist, p};
}

int getMinimumFuelCapacity(int a, int b){
   return mx == inf ? -1 : mx;
   auto [dist, p] = dijkstra(a);

   int mn = inf, v = p[b], pv = b;
   while(v != a){
      for(auto [ch, w] : g[v]){
         if(ch != pv and ch != p[v]) mn = min(mn, w);
      }
      pv = v;
      v = p[v];
   }

   auto [dist1, p1] = dijkstra(a, {a, pv});
   mn = min(mn, dist1[b]);
   auto [dist2, p2] = dijkstra(b, {b, p[b]});
   mn = min(mn, dist2[a]);

   int ans = max(dist[b], mn);
   return ans == inf ? -1 : ans;
}

• Subtask 1: 6 / 6
• Subtask 2: 0 / 7
• Subtask 3: 0 / 17
• Subtask 4: 0 / 20
• Subtask 5: 0 / 23
• Subtask 6: 0 / 27