Submission #1200685

#	Time	Username	Problem	Language	Result	Execution time	Memory
1200685		Mohamed_Kachef06	Swapping Cities (APIO20_swap)	C++17	0 / 100	2086 ms	589824 KiB

swap

#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
#include <vector>
#define all(x) x.begin() , x.end()


int n , m;
vector<int> u , v , w;
vector<vector<array<int ,3>>> adj; 

void init(int N, int M,vector<int> U, vector<int> V, vector<int> W) {
  n = N , m = M , u = U , v = V , w = W; 
  adj.assign(n , {}); 
  for (int i = 0 ; i < M ; i++){
    adj[U[i]].push_back({V[i] , W[i] , i});
    adj[V[i]].push_back({U[i] , W[i] , i}); 
  }
  int cnt = M; 
  for (int i = 0 ; i < N ;  i++) adj[i].push_back({i , 0 , cnt++}); 
}

bool check(int x , int y , int md){
    bool vis[n][n] = {}; 
    queue<array<int , 2>> qu; 
    vis[x][y] = 1;
    qu.push({x , y}); 
    while(!qu.empty()){
      auto &[x , y] = qu.front(); qu.pop(); 
      for (auto &[i , d , id1] : adj[x]){
        if (d > md) continue; 
        for (auto &[j  , e , id2] : adj[y]){
          if (i == j || d > md || e > md || id1 == id2) continue; 
          if (!vis[i][j]){
            vis[i][j] = 1; 
            qu.push({i , j}); 
          }
        }
      }
    }
    return vis[y][x]; 
}

int getMinimumFuelCapacity(int X, int Y) {
  //if (!check(X , Y , 1e9)) {return -1; }
  long long l = 0 , r = 1e9 , md;
  while(l<=r){
    md = (l+r)/2; 
    if (check(X , Y , md)) r = md-1;
    else l = md+1; 
  }
  int ans = (r >= 1e9 ? -1 : r+1);
   return 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