제출 #979583

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
979583		bubble_xd	자매 도시 (APIO20_swap)	C++17	13 / 100	331 ms	46992 KiB

swap

#include "swap.h"

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;

const int nax = 300005;
const int K = 23;

int fa[nax], front[nax], back[nax], val[nax];
bool chain[nax];
int N, M, id;
vector<pair<int, pair<int, int>>> edges; // (W, index)
vector<int> G[nax];
int sp[nax][K], dep[nax];

int find(int x) {
  if (x == fa[x]) return x;
  fa[x] = find(fa[x]);
  return fa[x];
}

void dfs(int u, int f) {
  dep[u] = dep[f] + 1;
  sp[u][0] = f;
  for (int i = 1; i < K; i++) sp[u][i] = sp[sp[u][i - 1]][i - 1];
  for (auto child : G[u]) dfs(child, u);
}

int lca(int u, int v) {
  if (dep[v] >= dep[u]) swap(u, v);
  for (int i = K - 1; i >= 0; i--) if (dep[sp[u][i]] >= dep[v]) u = sp[u][i];
  if (u == v) return u;
  for (int i = K - 1; i >= 0; i--) if (dep[sp[u][i]] != dep[sp[v][i]]) u = sp[u][i], v = sp[v][i];
  return sp[u][0];
}
void init(int _N, int _M, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
  N = _N; M = _M;
  for (int i = 0; i < M; i++) 
    edges.push_back(make_pair(W[i], make_pair(U[i], V[i])));
  sort(edges.begin(), edges.end());
  for (int i = 0; i < nax; i++) fa[i] = i;
  for (int i = 1; i <= N; i++) {
    chain[i] = true;
    front[i] = back[i] = i;
  }
  id = N;
  for (int i = 0; i < M; i++) {
    int w = edges[i].first;
    int u = edges[i].second.first + 1;
    int v = edges[i].second.second + 1;

    int A = find(u), B = find(v);
    if (A == B) {
      if (chain[A]) {
        int new_id = ++id;
        fa[A] = new_id;
        val[new_id] = w;
        G[new_id].push_back(A);
      }
      continue;
    }
    int new_id = ++id;
    fa[A] = new_id;
    fa[B] = new_id;
    val[new_id] = w;
    G[new_id].push_back(A);
    G[new_id].push_back(B);
    if (chain[A] && chain[B]) {
      if (front[A] == v || back[A] == v) swap(A, B);
      // connect u -> v 
      // x -> u -> v -> y
      if (front[A] == u) swap(front[A], back[A]);
      if (back[B] == v) swap(front[B], back[B]);
      if (back[A] == u && front[B] == v) {
        chain[new_id] = true;
        front[new_id] = front[A];
        back[new_id] = back[B];
      }
    }
  }
  dfs(id, 0);
}

int getMinimumFuelCapacity(int X, int Y) {
  X++; Y++;
  int l = lca(X, Y);
  if (!chain[l]) return val[l];
  for (int i = K - 1; i >= 0; i--) {
    if (sp[l][i] && chain[sp[l][i]]) {
      l = sp[l][i];
    }
  }
  if (l == id) return -1;
  return val[sp[l][0]];
}

// #include "grader.cpp"

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