Submission #1200814

#	Time	Username	Problem	Language	Result	Execution time	Memory
1200814		Mohamed_Kachef06	Swapping Cities (APIO20_swap)	C++17	0 / 100	2097 ms	45656 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<signed> u , v , w;
vector<vector<array<int ,3>>> adj; 
int mx = 0; 

void init(signed N, signed M,vector<signed> U, vector<signed> V, vector<signed> 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}); 
    mx = max(mx , W[i]); 
  }
  int cnt = M; 
  for (int i = 0 ; i < N ;  i++) adj[i].push_back({i , 0 , cnt++}); 
}

bool vis[1000][1000];

void dfs(int x , int y , int md){
  if (vis[x][y]) return;
  vis[x][y] = 1; 
  for (auto [i , d , id1] : adj[x]){
    for (auto [j , e , id2] : adj[y]){
      if (d > md || e > md || i == j || id1 == id2) continue;
      dfs(i , j, md);  
    }
  }
}

bool check(int x , int y , int md){
   if (md > 1e9) return 0;
   for (int i = 0 ; i < n ; i++){
    for (int j = 0 ; j < n ; j++) vis[i][j] = 0;
   }
     dfs(x , y , md);
    return vis[y][x]; 
}

signed getMinimumFuelCapacity(signed X, signed 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; 
  }
  return (r + 1 > 1e9 ? -1 : r+1);
}

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