Submission #788611

#	Time	Username	Problem	Language	Result	Execution time	Memory
788611		WLZ	Swapping Cities (APIO20_swap)	C++17	100 / 100	362 ms	75444 KiB

swap

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

struct edge {
  int u, v, w;
};

class dsu {
  private: vector<int> p, rank;    
  public:
    dsu(int n) {
      p.assign(n, -1);
      rank.assign(n, 0);
    }

    int root(int x) {
      if (p[x] == -1) {
        return x;
      }
      return (p[x] = root(p[x]));
    }

    bool same_set(int x, int y) {
      return (root(x) == root(y));
    }

    void connect(int x, int y) {
      x = root(x); y = root(y);
      if (x != y) {
        if (rank[x] > rank[y]) {
          p[y] = x;
        } else {
          p[x] = y;
          if (rank[x] == rank[y]) {
            rank[y]++;
          }
        }
      }
    }
};

int n, m, dfs_cnt = 0, max_log;
vector< vector<int> > g;
vector<bool> swappable;
vector<int> dfs_in, dfs_out;
vector< vector<int> > up;
vector<edge> edges;

void dfs(int u, int p) {
  //cout << u << endl;
  dfs_in[u] = dfs_cnt++;
  up[u][0] = p;
  for (int i = 1; i <= max_log; i++) {
    up[u][i] = up[up[u][i - 1]][i - 1];
  }
  for (auto& v : g[u]) {
    if (v != p) {
      dfs(v, u);
    }
  }
  dfs_out[u] = dfs_cnt++;
}

bool is_anc(int u, int v) {
  return (dfs_in[u] <= dfs_in[v] && dfs_out[u] >= dfs_out[v]);
}

int lca(int u, int v) {
  if (is_anc(u, v)) {
    return u;
  }
  if (is_anc(v, u)) {
    return v;
  }
  for (int i = max_log; i >= 0; i--) {
    if (!is_anc(up[u][i], v)) {
      u = up[u][i];
    }
  }
  return up[u][0];
}

int first_swappable(int u) {
  if (swappable[u]) {
    return u;
  }
  for (int i = max_log; i >= 0; i--) {
    if (!swappable[up[u][i]]) {
      u = up[u][i];
    }
  }
  if (u == n + m - 1) {
    return -1;
  }
  return up[u][0];
}

void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
  n = N; m = M;
  for (int i = 0; i < M; i++) {
    edges.push_back({U[i], V[i], W[i]});
  }
  sort(edges.begin(), edges.end(), [](const edge &a, const edge &b) {
    return a.w < b.w;
  });
  g.resize(n + m);
  swappable.assign(n + m, false);
  dsu conn(n);
  vector<int> deg(n, 0), cc(n);
  iota(cc.begin(), cc.end(), 0);
  for (int i = 0; i < m; i++) {
    int x = edges[i].u, y = edges[i].v;
    deg[x]++;
    deg[y]++;
    if (conn.same_set(x, y)) {
      g[cc[conn.root(x)]].push_back(n + i);
      g[n + i].push_back(cc[conn.root(x)]);
      swappable[n + i] = true;
      cc[conn.root(x)] = n + i;
    } else {      
      g[cc[conn.root(x)]].push_back(n + i);
      g[cc[conn.root(y)]].push_back(n + i);
      g[n + i].push_back(cc[conn.root(x)]);
      g[n + i].push_back(cc[conn.root(y)]);
      swappable[n + i] = (swappable[cc[conn.root(x)]] || swappable[cc[conn.root(y)]]);
      conn.connect(x, y);
      cc[conn.root(x)] = n + i;
      if (deg[x] >= 3 || deg[y] >= 3) {
        swappable[n + i] = true;
      }
    }
  }
  max_log = ceil(log2(n + m));
  dfs_in.resize(n + m);
  dfs_out.resize(n + m);
  up.assign(n + m, vector<int>(max_log + 1));
  dfs(n + m - 1, n + m - 1);
}

int getMinimumFuelCapacity(int X, int Y) {
  int u = first_swappable(lca(X, Y));
  if (u == -1) {
    return -1;
  }
  return edges[u - n].w;
}

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