Submission #824032

#	Time	Username	Problem	Language	Result	Execution time	Memory
824032		abczz	Swapping Cities (APIO20_swap)	C++14	100 / 100	689 ms	56112 KiB

swap

#include "swap.h"
#include <iostream>
#include <vector>
#include <array>
#include <algorithm>
#define ll long long
 
using namespace std;
 
ll cnt, P[200000];
ll X[200000], D[200000], bl[19][200000], in[200000];
array<ll, 2> chd[200000];
bool B[200000];
vector <array<ll, 3>> E;
ll dsu(ll u) {
  if (P[u] == u) return u;
  else return P[u] = dsu(P[u]);
}
 
void dfs(ll u, ll w) {
  if (u == -1) return;
  D[u] = w;
  dfs(chd[u][0], w+1);
  dfs(chd[u][1], w+1);
}
 
ll lca(ll a, ll b) {
  if (D[a] < D[b]) swap(a, b);
  ll da = D[a];
  for (int i=18; i>=0; --i) {
    if (da-D[b] >= (1LL<<i)) {
      da -= (1LL<<i);
      a = bl[i][a];
    }
  }
  for (int i=18; i>=0; --i) {
    if (bl[i][a] != bl[i][b]) {
      a = bl[i][a], b = bl[i][b];
    }
  }
  if (a != b) {
    a = bl[0][a], b = bl[0][b];
  }
  for (int i=18; i>=0; --i) {
    if (!B[bl[i][a]]) {
      a = bl[i][a];
    }
  }
  if (!B[a]) a = bl[0][a];
  return B[a] == 1 ? X[a] : -1;
}
 
void init(int N, int M,
          std::vector<int> U, std::vector<int> V, std::vector<int> W) {
  ll a, b;
  for (int i=0; i<N; ++i) {
    chd[i] = {-1, -1};
  }
  for (int i=0; i<2*N; ++i) {
    P[i] = i;
    X[i] = 1e18;
  }
  for (int i=0; i<M; ++i) {
    E.push_back({W[i], U[i], V[i]});
  }
  cnt = N;
  sort(E.begin(), E.end());
  for (auto [w, u, v] : E) {
    ++in[u], ++in[v];
    a = dsu(u), b = dsu(v);
    if (a != b) {
      bl[0][a] = bl[0][b] = cnt;
      chd[cnt] = {a, b};
      P[a] = P[b] = cnt;
      B[cnt] = B[a] | B[b];
      X[cnt] = w;
      if (in[u] >= 3 || in[v] >= 3) {
        B[cnt] = 1;
        X[cnt] = w;
      }
      ++cnt;
    }
    else if (!B[a]) {
      B[a] = 1;
      X[a] = w;
    }
  }
  --cnt;
  dfs(cnt, 0);
  bl[0][cnt] = cnt;
  for (int i=1; i<19; ++i) {
    for (int j=0; j<=cnt; ++j) {
      bl[i][j] = bl[i-1][bl[i-1][j]];
    }
  }
}
 
int getMinimumFuelCapacity(int X, int Y) {
  return lca(X, Y);
}

Compilation message (stderr)

swap.cpp: In function 'void init(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
swap.cpp:68:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   68 |   for (auto [w, u, v] : E) {
      |             ^

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