Submission #916166

#	Time	Username	Problem	Language	Result	Execution time	Memory
916166		duckindog	Swapping Cities (APIO20_swap)	C++14	13 / 100	192 ms	42568 KiB

swap

#include<bits/stdc++.h>

using namespace std;

//#define LOCAL

#ifndef LOCAL
#include "swap.h"
#endif // LOCAL

const int N = 2e5 + 10;
struct edge {
  int u, v, w;
  edge() : u(0), v(0), w(0) {}
  edge(int u, int v, int w) : u(u), v(v), w(w) {}
} ED[N];
int par[N], id[N];
int root(int u, int ty = 0) {
  if (ty) return (id[u] < 0 ? u : id[u] = root(id[u], ty));
  return (par[u] < 0 ? u : par[u] = root(par[u]));
}
void add(int u, int v, int ty = 0) {
  u = root(u, ty); v = root(v, ty);
  if (u == v) return;
  if (ty) {
    if (u < v) swap(u, v);
    id[u] += id[v];
    id[v] = u;

  } else {
    if (par[u] > par[v]) swap(u, v);
    par[u] += par[v];
    par[v] = u;
  }
}

int n, m;
vector<int> ad[N];
bool mk[N];
int cnt[N], weight[N];
int low[N];

int f[N][17], st[N], ed[N], it;
void dfs(int u, int pre = -1) {
  if (mk[u]) low[u] = weight[u];
  st[u] = ++it;
  for (int i = 1; i <= 16; ++i)
    f[u][i] = f[f[u][i - 1]][i - 1];

  for (int v : ad[u]) {
    if (v == pre) continue;
    if (!mk[v]) low[v] = low[u];
    f[v][0] = u;
    dfs(v, u);
  }
  ed[u] = it;
}
bool anc(int u, int v) {
  return st[u] <= st[v] && ed[u] >= ed[v];
}
int lca(int u, int v) {
  if (anc(u, v)) return u;
  if (anc(v, u)) return v;
  for (int i = 16; i >= 0; --i)
    if (!anc(f[u][i], v)) u = f[u][i];
  return f[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) {
    int u = U[i], v = V[i], w = W[i];
    ED[i] = {u, v, w};
  }
  sort(ED, ED + m, [&] (const auto& a, const auto& b) {
    return a.w < b.w;
  });

  memset(par, -1, sizeof par);
  memset(id, -1, sizeof id);
  int it = n - 1;
  for (int i = 0; i < m; ++i) {
    int u = ED[i].u, v = ED[i].v, w = ED[i].w;
    cnt[u] += 1; cnt[v] += 1;
    if ((cnt[u] >= 3 || cnt[v] >= 3) && !mk[it]) {
      mk[it] = 1;
      weight[it] = w;
    }
    if (root(u) == root(v)) {
      if (!mk[it]) {
        mk[it] = 1;
        weight[it] = w;
      }
      continue;
    }
    add(u, v);
    it += 1;
    u = root(u, 1); v = root(v, 1);

    ad[it].push_back(u); ad[it].push_back(v);
    mk[it] |= (mk[u] | mk[v]);

    add(it, u, 1); add(it, v, 1);
    weight[it] = w;
  }
  memset(low, -1, sizeof low);
  dfs(f[it][0] = it);
}

int getMinimumFuelCapacity(int X, int Y) {
  return low[lca(X, Y)];
}

#ifdef LOCAL
int32_t main() {
  cin.tie(0)->sync_with_stdio(0);

  if (fopen("duck.inp", "r")) {
    freopen("duck.inp", "r", stdin);
    freopen("duck.out", "w", stdout);
  }

  int n, m; cin >> n >> m;
  vector<int> U(m), V(m), W(m);
  for (int i = 0; i < m; ++i) cin >> U[i] >> V[i] >> W[i];
  init(n, m, U, V, W);

  int q; cin >> q;
  for (int i = 1; i <= q; ++i) {
    int X, Y; cin >> X >> Y;
    cout << getMinimumFuelCapacity(X, Y) << '\n';
  }


}
#endif // LOCAL

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