Submission #1209270

#	Time	Username	Problem	Language	Result	Execution time	Memory
1209270		vincentbucourt1	Swapping Cities (APIO20_swap)	C++20	13 / 100	203 ms	50888 KiB

swap

#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second

struct DSU {
  vector<int> par;
  DSU (int n) {
    par.resize(n);
    iota(par.begin(), par.end(), 0);
  }
  int get (int x) {
    if (par[x] == x) return x;
    else return par[x] = get(par[x]);
  }
  bool combine (int x, int y) {
    x = get(x), y = get(y);
    if (x == y) return false;
    par[x] = y;
    return true;
  }
  bool sameCC (int x, int y) {
    return get(x) == get(y);
  }
};

struct Edge {
  int u, v, w;
  int move (int x) {
    if (u == x) return v;
    else return u;
  }
};
bool cmpEdge (const Edge& a, const Edge& b) {
  return a.w < b.w;
}

const int INF = (int)1e18;

int numV, numE;
vector<Edge> edges;
vector<vector<int>> adj;
vector<vector<int>> mst;
vector<int> SP;
vector<int> depth;
vector<vector<int>> jump, jumpMax;

void dfs (int node, int par) {
  for (int iEdge : mst[node]) {
    Edge edgeOn = edges[iEdge];
    int child = edgeOn.move(node), weight = edgeOn.w;
    if (child == par);
    jump[child][0] = node;
    jumpMax[child][0] = weight;
    depth[child] = depth[node] + 1;
    dfs(child, node);
  }
}

void init(int N, int M,
          std::vector<int> U, std::vector<int> V, std::vector<int> W) {
  numV = N, numE = M;
  edges.resize(numE);
  adj.resize(numV);
  mst.resize(numV);
  SP.assign(numV, INF);
  jump.assign(numV, vector<int>(32));
  jumpMax.assign(numV, vector<int>(32, 0));
  depth.resize(numV);

  for (int i = 0; i < numE; i++) {
    edges[i] = Edge{U[i], V[i], W[i]};
  }
  sort(edges.begin(), edges.end(), cmpEdge);
  for (int i = 0; i < numE; i++) {
    Edge edgeOn = edges[i];
    adj[edgeOn.u].push_back(i);
    adj[edgeOn.v].push_back(i);
  }

  DSU dsu(numV);
  for (int i = 0; i < numE; i++) {
    Edge edgeOn = edges[i];
    if (!dsu.sameCC(edgeOn.u, edgeOn.v)) {
      mst[edgeOn.u].push_back(i);
      dsu.combine(edgeOn.u, edgeOn.v);
    }
    else {
      SP[edgeOn.u] = min(SP[edgeOn.u], edgeOn.w);
      SP[edgeOn.v] = min(SP[edgeOn.v], edgeOn.w);
    }
  }

  for (int i = 0; i < numV; i++) {
    if ((int)adj[i].size() >= 3) {
      SP[i] = min(SP[i], edges[adj[i][2]].w);
    }
  }

  priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> PQ;
  for (int i = 0; i < numV; i++) {
    PQ.push({SP[i], i});
  }
  while (!PQ.empty()) {
    pair<int,int> on = PQ.top();
    PQ.pop();
    int nodeOn = on.s, valOn = on.f;
    if (SP[nodeOn] < valOn) {
      continue;
    }
    for (int iEdge : adj[nodeOn]) {
      Edge edgeNxt = edges[iEdge];
      int nodeNxt = edgeNxt.move(nodeOn), weight = edgeNxt.w;
      if (SP[nodeNxt] > max(SP[nodeOn], weight)) {
        SP[nodeNxt] = max(SP[nodeOn], weight);
        PQ.push({SP[nodeNxt], nodeNxt});
      }
    }
  }

  depth[0] = 0;
  dfs(0, -1);
  for (int len = 1; len < 32; len++) {
    for (int i = 0; i < numV; i++) {
      jump[i][len] = jump[jump[i][len-1]][len-1];
      jumpMax[i][len] = max(jumpMax[i][len-1], jumpMax[jump[i][len-1]][len-1]);
    }
  }
}

int getMinimumFuelCapacity(int X, int Y) {
  int ans = max(ans, min(SP[X], SP[Y]));

  int lo = X, hi = Y;
  if (lo == hi) {
    if (ans == INF) return -1;
    else return ans;
  }
  if (depth[hi] > depth[lo]) {
    swap(lo, hi);
  }
  for (int len = 31; len >= 0; len--) {
    if (depth[jump[lo][len]] >= depth[hi]) {
      ans = max(ans, jumpMax[lo][len]);
      lo = jump[lo][len];
    }
  }
  assert(depth[lo] == depth[hi]);
  if (lo == hi) {
    if (ans == INF) return -1;
    else return ans;
  }
  for (int len = 31; len >= 0; len--) {
    if (jump[lo][len] != jump[hi][len]) {
      ans = max({ans, jumpMax[lo][len], jumpMax[hi][len]});
      lo = jump[lo][len];
      hi = jump[hi][len];
    }
  }
  assert(jump[lo][0] == jump[hi][0]);
  ans = max({ans, jumpMax[lo][0], jumpMax[hi][0]});
  
  if (ans == INF) return -1;
  else return ans;
}

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