Submission #1200825

#	Time	Username	Problem	Language	Result	Execution time	Memory
1200825		Mohamed_Kachef06	Swapping Cities (APIO20_swap)	C++17	17 / 100	2094 ms	14328 KiB

swap

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

const int N = 1e5;
int n , m;
vector<int> u , v , w;

vector<vector<array<int , 2>>> 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 , {});
}

bool vis[N] ; 
int edges = 0; 
int nodes = 0; 
bool f = 0; 

void dfs(int x ,  vector<vector<int>> &adj){
    if (vis[x]) return ; 
    vis[x] = 1; 
    nodes++; 
    if (adj[x].size() > 2) f = 1; 
    for (auto i : adj[x]){
      edges++; 
      dfs(i , adj); 
    }
}

bool check(int x , int y , int md){
  vector<vector<int>> adj(n);  
  for (int i  =0 ; i < n; i++) vis[i] = 0; 
  nodes = 0; edges = 0; f = 0; 
  for (int i = 0 ; i < m ; i++){
    if (w[i] > md) continue; 
    adj[u[i]].push_back(v[i]);
    adj[v[i]].push_back(u[i]);
  }
  dfs(x , adj); 
  if (!vis[y]) return 0; 
  edges/=2; 
  //cout << nodes << ' ' << edges << ' ' << md << ' '; 
  //cout << f << '\n';
  if (edges > nodes - 1) return 1; 
  return f; 
}



int getMinimumFuelCapacity(int X, int Y) {
  int 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: 17 / 17
• Subtask 4: 0 / 20
• Subtask 5: 0 / 23
• Subtask 6: 0 / 27