Submission #964087

#	Time	Username	Problem	Language	Result	Execution time	Memory
964087		efedmrlr	Swapping Cities (APIO20_swap)	C++17	0 / 100	2011 ms	21260 KiB

swap

// #pragma GCC optimize("O3,Ofast,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include "swap.h"
#include <bits/stdc++.h>

using namespace std;


#define lli long long int
#define MP make_pair
#define pb push_back
#define REP(i,n) for(int i = 0; (i) < (n); (i)++)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()


void fastio() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}


const double EPS = 0.00001;
const int INF = 1e9+500;
const int ALPH = 26;
const int LGN = 25;
constexpr int MOD = 1e9+7;
int n,m;

vector<vector<array<int, 2> > > adj;
vector<array<int,3> > edges;
void init(int N, int M,
          std::vector<int> U, std::vector<int> V, std::vector<int> W) {
    adj.assign(N + 1, vector<array<int,2> >());
    n = N; m = M;
    edges.resize(M);
    for(int i = 0; i < m; i++) {
      adj[U[i]].pb({V[i], W[i]});
      adj[V[i]].pb({U[i], W[i]});
      edges[i] = {U[i], V[i], W[i]};
    }

}

void dijkstra(int src, vector<int> &sp, vector<vector<array<int,2> > > &ad, vector<int> &pr) {
  priority_queue<array<int,2>, vector<array<int,2> >, greater<array<int,2> > > pq;
  sp.assign(n, INF);
  pr.assign(n, -1);
  pq.push({0, src});
  while(pq.size()) {
    auto cur = pq.top();
    pq.pop();
    if(sp[cur[1]] != INF) {
      continue;
    }
    // cout << cur[1] << " :" << cur[0] << "\n";
    sp[cur[1]] = cur[0];
    for(auto c : ad[cur[1]]) {
      if(sp[c[0]] != INF) continue;
      pq.push({max(cur[0] , c[1]), c[0]});
      pr[c[0]] = cur[1];

    }
  }
}

int getMinimumFuelCapacity(int X, int Y) {
  vector<int> sp, pr;
  dijkstra(X, sp, adj, pr);
  int cost = sp[Y];
  int ext = INF;
  
  
  int x = Y;
  vector<vector<array<int,2> > > tmp(adj);
  int cost2 = sp[Y];
  while(x != X) {
    // cout << x << " " << pr[x] << endl;
    assert(pr[x] != -1);
    for(auto itr = tmp[x].begin(); itr != tmp[x].end(); itr++) {
      if((*itr)[0] == pr[x]) {
        tmp[x].erase(itr);
        break;
      }
    }
    for(auto itr = tmp[pr[x]].begin(); itr != tmp[pr[x]].end(); itr++) {
      if((*itr)[0] == x) {
        tmp[pr[x]].erase(itr);
        break;
      }
    }
    x = pr[x];

  }
  for(int i = 0; i < n; i++) {
    if(i == X || i == Y) continue;
    if(sp[i] <= cost) {
      for(auto c : tmp[i]) {
        ext = min(ext, c[1]);
      }
    }
  }
  cost = max(cost, ext);
  dijkstra(X, sp, tmp, pr);
  cost2 = max(cost2, sp[Y]);
  if(min(cost2, cost) == INF) return -1; 
  // cout << endl;
  return min(cost2, cost);
}

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