Submission #1285979

#	Time	Username	Problem	Language	Result	Execution time	Memory
1285979		lmquan	Swapping Cities (APIO20_swap)	C++20	100 / 100	237 ms	40284 KiB

swap

#define taskname "SwappingCities"
#include <bits/stdc++.h>
using namespace std;
const int kMaxLog = 19;
const int kInf = 2e9;

struct DSUTree {
  int x, timer;
  vector<int> parent, deg, max_deg, edges, sz, in, out, k;
  vector<vector<int>> g, jump;

  DSUTree(int _x = 0) : x(_x), edges(0), max_deg(0), timer(0) {
    parent.resize(x + 1);
    deg.resize(x + 1);
    max_deg.resize(x + 1);
    edges.resize(x + 1);
    sz.resize(x + 1, 0);
    g.resize(x + 1);
    for (int i = 1; i <= x; i++) {
      sz[i] = 1;
      parent[i] = i;
      deg[i] = max_deg[i] = edges[i] = 0;
    }
  }

  int FindSet(int u) {
    return (parent[u] == u ? u : parent[u] = FindSet(parent[u]));
  }

  bool Unite(int u, int v) {
    int cu = FindSet(u), cv = FindSet(v);
    if (cu == cv) {
      deg[u]++, deg[v]++;
      max_deg[cu] = max({max_deg[cu], deg[u], deg[v]});
      edges[cu]++;
      return (max_deg[cu] >= 3 || edges[cu] >= sz[cu]);
    }
    parent[cu] = parent[cv] = ++x;
    parent.push_back(x);
    g.push_back({cu, cv});
    sz.push_back(sz[cu] + sz[cv]);
    edges.push_back(edges[cu] + edges[cv] + 1);
    deg[u]++, deg[v]++;
    max_deg.push_back(max({max_deg[cu], max_deg[cv], deg[u], deg[v]}));
    return (max_deg[x] >= 3 || edges[x] >= sz[x]);
  }

  void DFS(int u) {
    in[u] = ++timer;
    for (int v : g[u]) {
      jump[0][v] = u;
      for (int i = 1; i < kMaxLog; i++) {
        jump[i][v] = jump[i - 1][jump[i - 1][v]];
      }
      k[v] = min(k[v], k[u]);
      DFS(v);
    }
    out[u] = timer;
  }

  bool Ancestor(int u, int v) {
    return (in[u] <= in[v] && out[v] <= out[u]);
  }

  int LCA(int u, int v) {
    if (Ancestor(u, v)) {
      return u;
    }
    for (int i = kMaxLog - 1; i >= 0; i--) {
      if (jump[i][u] >= 1 && !Ancestor(jump[i][u], v)) {
        u = jump[i][u];
      }
    }
    return jump[0][u];
  }
};

DSUTree a;
vector<pair<int, int>> S;

void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
  vector<int> p(M);
  iota(p.begin(), p.end(), 0);
  sort(p.begin(), p.end(), [&](int x, int y) {
    return W[x] < W[y];
  });
  a = DSUTree(N);
  for (int i = 0; i < M; i++) {
    U[p[i]]++, V[p[i]]++;
    if (a.Unite(U[p[i]], V[p[i]])) {
      S.push_back({a.FindSet(U[p[i]]), W[p[i]]});
    }
  }
  a.in.resize(a.x + 1);
  a.out.resize(a.x + 1);
  a.jump.resize(kMaxLog, vector<int>(a.x + 1));
  a.k.resize(a.x + 1, kInf);
  for (auto i : S) {
    a.k[i.first] = min(a.k[i.first], i.second);
  }
  a.DFS(a.x);
}

int getMinimumFuelCapacity(int X, int Y) {
  X++, Y++;
  int Z = a.LCA(X, Y);
  return (a.k[Z] == kInf ? -1 : a.k[Z]);
}

//int main() {
//  int N, M;
//  vector<int> U, V, W;
//  cin >> N >> M;
//  for (int i = 1; i <= M; i++) {
//    int u, v, w;
//    cin >> u >> v >> w;
//    U.push_back(u);
//    V.push_back(v);
//    W.push_back(w);
//  }
//  init(N, M, U, V, W);
//  int Q;
//  cin >> Q;
//  while (Q--) {
//    int X, Y;
//    cin >> X >> Y;
//    cout << getMinimumFuelCapacity(X, Y) << '\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