Submission #1184822

#	Time	Username	Problem	Language	Result	Execution time	Memory
1184822		loom	Swapping Cities (APIO20_swap)	C++20	0 / 100	2095 ms	13080 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 n, m;

void init(int n_, int m_, vector<int> u, vector<int> v, vector<int> w){
   n = n_, m = m_;
   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]});
   }
}

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), p(n);
   pq.push({0, s});
   dist[s] = 0;
   p[s] = s;

   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){
   auto [dist1, p1] = dijkstra(a);
   auto [dist2, p2] = dijkstra(b);
   auto [dist, p] = dijkstra(a, {a, p2[a]});

   int ans = dist[b];

   for(int i=0; i<n; i++){
      if(g[i].size() < 3) continue;
      sort(g[i].begin(), g[i].end());

      int mx = 0, c = 0;
      for(auto [ch, w] : g[i]){
         if(ch == p1[i] or ch == p2[i]) mx = max(mx, w), c++;
      }

      for(auto [ch, w] : g[i]){
         if(c < 3 and ch != p1[i] and ch != p2[i]) mx = max(mx, w), c++;
      }

      ans = min(ans, max(max(dist1[i], dist2[i]), mx));
   }

   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