Submission #1248910

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248910		kunzaZa183	Swapping Cities (APIO20_swap)	C++20	100 / 100	318 ms	59024 KiB

swap

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

vector<vector<int>> bin;
vector<int> depvi;
const int logn = 20;

vector<int> w;
vector<int> alledges;
vector<bool> lin;

int n;
void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
  w = W;
  n = N;
  vector<int> dsu(N);
  iota(dsu.begin(), dsu.end(), 0);
  function<int(int)> par = [&](int cur) {
    if (dsu[cur] == cur)
      return cur;
    return dsu[cur] = par(dsu[cur]);
  };

  alledges = vector<int>(M);
  iota(alledges.begin(), alledges.end(), 0);
  sort(alledges.begin(), alledges.end(),
       [&](int a, int b) { return W[a] < W[b]; });

  vector<vector<int>> adj(N);
  vector<pair<int, int>> vpii(N);
  for (int i = 0; i < N; i++)
    vpii[i] = {i, i};
  lin = vector<bool>(N, 1);

  for (auto in : alledges) {
    adj.push_back({});
    dsu.push_back(dsu.size());
    vpii.push_back({-1, -1});
    lin.push_back(0);
    if (par(U[in]) != par(V[in])) {
      adj.back().push_back(par(U[in])), adj.back().push_back(par(V[in]));
      if (!lin[par(U[in])] || !lin[par(V[in])])
        lin.back() = 0;
      else if ((U[in] == vpii[par(U[in])].first ||
                U[in] == vpii[par(U[in])].second) &&
               (V[in] == vpii[par(V[in])].first ||
                V[in] == vpii[par(V[in])].second)) {
        lin.back() = 1;
        multiset<int> si;
        si.insert(vpii[par(U[in])].first);
        si.insert(vpii[par(U[in])].second);
        si.insert(vpii[par(V[in])].first);
        si.insert(vpii[par(V[in])].second);
        si.erase(si.find(U[in]));
        si.erase(si.find(V[in]));
        vpii.back() = {*si.begin(), *si.rbegin()};
      } else {
        lin.back() = 0;
      }
    } else {
      adj.back().push_back(par(U[in]));
      lin.back() = 0;
    }
    dsu[par(U[in])] = dsu.back(), dsu[par(V[in])] = dsu.back();
  }

  bin = vector<vector<int>>(logn, vector<int>(N + M));
  depvi = vector<int>(N + M);

  function<void(int, int, int)> fvii = [&](int cur, int par, int dep) {
    bin[0][cur] = par;
    depvi[cur] = dep;

    for (auto a : adj[cur])
      fvii(a, cur, dep + 1);
  };
  fvii(N + M - 1, N + M - 1, 0);

  for (int i = 1; i < logn; i++)
    for (int j = 0; j < N + M; j++)
      bin[i][j] = bin[i - 1][bin[i - 1][j]];
}

int getMinimumFuelCapacity(int X, int Y) {

  if (lin.back() == 1)
    return -1;

  int tmpx = X, tmpy = Y;
  if (depvi[tmpx] > depvi[tmpy])
    swap(tmpx, tmpy);

  for (int i = logn - 1; i >= 0; i--) {
    if ((depvi[tmpy] - depvi[tmpx]) & (1 << i)) {
      tmpy = bin[i][tmpy];
    }
  }

  for (int i = logn - 1; i >= 0; i--) {
    if (bin[i][tmpx] != bin[i][tmpy])
      tmpx = bin[i][tmpx], tmpy = bin[i][tmpy];
  }
  if (tmpx != tmpy) {
    tmpx = bin[0][tmpx], tmpy = bin[0][tmpy];
  }

  int lca = tmpx;

  if (!lin[lca])
    return w[alledges[lca - n]];

  for (int i = logn - 1; i >= 0; i--) {
    if (lin[bin[i][lca]]) {
      lca = bin[i][lca];
    }
  }

  lca = bin[0][lca];

  return w[alledges[lca - n]];
}

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