Submission #1116416

#	Time	Username	Problem	Language	Result	Execution time	Memory
1116416		vjudge1	Swapping Cities (APIO20_swap)	C++17	0 / 100	4 ms	23120 KiB

swap

#include "swap.h"

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

template<size_t D>
void upd(array<int, D> &ar, int x) {
  for (size_t i = 0; i < D; ++i) {
    if (x < ar[i]) {
      swap(x, ar[i]);
    }
  }
}

const int N = 1e5 + 5, LG = 17, inf = 1e9 + 5;

int n, m;
int lab[N], dep[N], pr[LG][N], sp[LG][N], cost[LG][N], out[N];
array<int, 2> h[N];
vector<array<int, 2>> g[N];

int find(int u) {
  return lab[u] ^ u ? lab[u] = find(lab[u]) : u;
}

void dfs(int u, int p) {
  for (auto [v, w] : g[u]) {
    if (v ^ p) {
      cost[0][v] = w;
      pr[0][v] = u;
      dep[v] = dep[u] + 1;
      dfs(v, u);
      upd(h[u], w);
    }
  }
  for (auto [v, w] : g[u]) {
    if (v ^ p) {
      sp[0][v] = min(out[v], h[u][h[u][0] == w]);
    }
  }
}

void init(int n, int m, vector<int> u, vector<int> v, vector<int> w) {
  iota(lab + 1, lab + n + 1, 1);
  vector<array<int, 3>> e;
  for (int i = 0; i < m; ++i) {
    ++u[i], ++v[i];
    e.push_back({w[i], u[i], v[i]});
  }
  sort(e.begin(), e.end());
  memset(sp, 0x3f, sizeof(sp));
  memset(out, 0x3f, sizeof(out));
  memset(cost, 0x3f, sizeof(cost));
  for (int i = 0; i <= n; ++i) {
    h[i] = {inf, inf};
  }
  for (auto [w, u, v] : e) {
    if (find(u) == find(v)) {
      out[u] = min(out[u], w);
      out[v] = min(out[v], w);
    } else {
      lab[find(u)] = find(v);
      g[u].push_back({v, w});
      g[v].push_back({u, w});
    }
  }
  dfs(1, 1);
  for (int i = 1; i < LG; ++i) {
    for (int u = 1; u <= n; ++u) {
      pr[i][u] = pr[i - 1][pr[i - 1][u]];
      cost[i][u] = max(cost[i - 1][u], cost[i - 1][pr[i - 1][u]]);
      sp[i][u] = min(sp[i - 1][u], sp[i - 1][pr[i - 1][u]]);
    }
  }
}

int lca(int u, int v) {
  if (dep[u] < dep[v]) {
    swap(u, v);
  }
  for (int i = LG - 1; ~i; --i) {
    if (dep[u] - (1 << i) >= dep[v]) {
      u = pr[i][u];
    }
  }
  if (u == v) {
    return u;
  }
  for (int i = LG - 1; ~i; --i) {
    if (pr[i][u] ^ pr[i][v]) {
      u = pr[i][u], v = pr[i][v];
    }
  }
  return pr[0][u];
}

int getMinimumFuelCapacity(int u, int v) {
  ++u, ++v;
  int res = 0, add = inf;
  int x = lca(u, v);
  add = min({add, out[x], cost[0][x]});
  if (u != x) {
    add = min(add, h[u][0]);
  }
  if (v != x) {
    add = min(add, h[v][0]);
  }
  for (int i = LG - 1; ~i; --i) {
    if (dep[u] - (1 << i) >= dep[x]) {
      res = max(res, cost[i][u]);
      add = min(add, sp[i][u]);
      u = pr[i][u];
    }
    if (dep[v] - (1 << i) >= dep[x]) {
      res = max(res, cost[i][v]);
      add = min(add, sp[i][v]);
      v = pr[i][v];
    }
  }
  return add == inf ? -1 : max(add, res);
}

// you'll be the best but now you're just trash

// int main() {
//   int N, M;
//   assert(2 == scanf("%d %d", &N, &M));
//   std::vector<int> U(M), V(M), W(M);
//   for (int i = 0; i < M; ++i) {
//     assert(3 == scanf("%d %d %d", &U[i], &V[i], &W[i]));
//   }
//   int Q;
//   assert(1 == scanf("%d", &Q));
//   std::vector<int> X(Q), Y(Q);
//   for (int i = 0; i < Q; ++i) {
//     assert(2 == scanf("%d %d", &X[i], &Y[i]));
//   }
//   init(N, M, U, V, W);
//   std::vector<int> minimum_fuel_capacities(Q);
//   for (int i = 0; i < Q; ++i) {
//     minimum_fuel_capacities[i] = getMinimumFuelCapacity(X[i], Y[i]);
//   }
//   for (int i = 0; i < Q; ++i) {
//     printf("%d\n", minimum_fuel_capacities[i]);
//   }
//   return 0;
// }

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