Submission #1183888

#	Time	Username	Problem	Language	Result	Execution time	Memory
1183888		loom	Swapping Cities (APIO20_swap)	C++20	0 / 100	202 ms	15416 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];
multiset<int> st;
int wt[N];

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]});
      wt[u[i] == 0 ? v[i] : u[i]] = w[i];
      st.insert(w[i]);
   }
}

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){
   if(a == 0 or b == 0) return -1;
   st.erase(st.find(wt[a]));
   st.erase(st.find(wt[b]));
   int rtn = (st.empty() ? -1 : *st.begin());
   st.insert(wt[a]);  
   st.insert(wt[b]);  
   return rtn;

   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: 0 / 6
• Subtask 2: 0 / 7
• Subtask 3: 0 / 17
• Subtask 4: 0 / 20
• Subtask 5: 0 / 23
• Subtask 6: 0 / 27