Submission #807534

#	Time	Username	Problem	Language	Result	Execution time	Memory
807534		dong_liu	Swapping Cities (APIO20_swap)	C++17	100 / 100	322 ms	52368 KiB

swap

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

#include "swap.h"

typedef vector<int> vi;

const int N = 3e5, L = 19, INF = int(1e9) + 1;

int p[N];

int find(int i) { return p[i] == i ? i : p[i] = find(p[i]); }

int tag1[N], tag2[N], ans[N];
vi g[N];

int pp[L][N], dd[N];

void dfs(int p, int i) {
  pp[0][i] = p;
  for (int l = 1; l < L; l++) pp[l][i] = pp[l - 1][pp[l - 1][i]];
  ans[i] = min(ans[i], max(tag1[i], tag2[i]));
  for (int j : g[i]) {
    dd[j] = dd[i] + 1;
    ans[j] = min(ans[j], ans[i]);
    dfs(i, j);
  }
}

int lca(int i, int j) {
  if (dd[i] < dd[j]) swap(i, j);
  int k = dd[i] - dd[j];
  for (int l = 0; l < L; l++)
    if (k >> l & 1) i = pp[l][i];
  if (i == j) return i;
  for (int l = L - 1; l >= 0; l--)
    if (pp[l][i] != pp[l][j]) i = pp[l][i], j = pp[l][j];
  return pp[0][i];
}

void init(int n, int m, vi u, vi v, vi w) {
  vi order(m);
  for (int i = 0; i < m; i++) order[i] = i;
  sort(order.begin(), order.end(), [&](int i, int j) { return w[i] < w[j]; });
  vi d(n);
  for (int i = 0; i < n + m; i++) {
    p[i] = i;
    ans[i] = tag1[i] = tag2[i] = INF;
  }
  int root = -1;
  for (int h : order) {
    int i = u[h], j = v[h];
    d[i]++;
    d[j]++;
    bool swap = d[i] >= 3 || d[j] >= 3;
    if (find(i) != find(j)) {
      g[n + h].push_back(find(i));
      g[n + h].push_back(find(j));
      tag1[n + h] = min(tag1[n + h], w[h]);
      tag2[n + h] = min(tag2[find(i)], tag2[find(j)]);
      if (swap) tag2[n + h] = min(tag2[n + h], w[h]);
      p[find(i)] = p[find(j)] = n + h;
      root = n + h;
    } else {
      int c = find(i);
      tag2[c] = min(tag2[c], w[h]);
    }
  }
  dfs(root, root);
}

int getMinimumFuelCapacity(int i, int j) {
  int p = lca(i, j);
  return ans[p] == INF ? -1 : ans[p];
}

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