Submission #741403

#	Time	Username	Problem	Language	Result	Execution time	Memory
741403		vjudge1	Swapping Cities (APIO20_swap)	C++17	0 / 100	2080 ms	15068 KiB

swap

#include "swap.h"

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5;
const int M = 2e5 + 5;
const int MAXA = 1e9 + 7;
int n, m;
array<int, 3> edge[M];
vector <int> a[N];
int ma = 0;
bool vis[N];

void init(int N, int M, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
  n = N; m = M;
  for(int i = 0; i < m; ++i){
    edge[i] = {U[i], V[i], W[i]};
    ma = max(ma, W[i]);
    //a[U[i]].push_back({V[i], W[i]});
    //a[V[i]].push_back({U[i], W[i]});
  }
}

bool dfs(int u, int par, int Y){
  vis[u] = true;
  if (u == Y) return false;

  for(int i : a[u]){
    if (i == par) continue;
    if (vis[i]) return true;

    bool g = dfs(i, u, Y);
    if (g) return true;  
  }

  return false;
}

bool f(int mid, int X, int Y){
  for(int i = 0; i < n; ++i) a[i].clear(), vis[i] = false;
  for(int i = 0; i < m; ++i){
    if (edge[i][2] <= mid) {
      a[edge[i][0]].push_back(edge[i][1]);
      a[edge[i][1]].push_back(edge[i][0]);
    }
  }
  return dfs(X, -1, Y);
}

int getMinimumFuelCapacity(int X, int Y) {
  int l = 0, r = MAXA;
  while (l + 1 < r){
    int mid = (l + r) >> 1;
    if (f(mid, X, Y)) r = mid;
    else l = mid;
  }
  if (r == MAXA) r = -1;

  return r;
}

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