---
lang: ja-jp
tags: APIO
---
# APIO 2020-B 都市の代表者の交換 (Swapping Cities)

不等号に注意

## 問題文

https://apio2020.toki.id/assets/statements/swap_ja.pdf
https://oj.uz/problem/view/APIO20_swap

$N$ 頂点 $M$ 辺の重み付き無向グラフが与えられる。 $Q$ 回の以下のクエリにオンラインで答えよ。

頂点 $X, Y$ から同時に車が $1$ 台出発し、頂点 $Y, X$ に向かう。
しかし、道は車 1 台分の幅しかないので、途中で方向を変えたり、すれ違ったりできない。
$2$ 台の車が通る辺の重みの最大値の最小値は？

$N ≤ 10^5$
$M ≤ 2 \times 10^5$
$Q ≤ 2 \times 10^5$

## 考察

最大値の最小値なので答え決め打ち二分探索 [典型]

重み $K$ 以下の辺のみからなる重みなし無向グラフで考える。
まず $X, Y$ は連結である必要がある。
連結成分に閉路が存在すれば、閉路を回ることですれ違うことができる。

それ以外の方法がないか考えてみる。

実は、次数 $3$ の頂点の周りも $1$ つに退避させることですれ違うことができる。

閉路がなくて次数 $2$ 以下ならばパスグラフなので、すれ違えない。

オンラインで、重み $K$ 以下の辺のみを使ったときの

- 連結性
- 連結成分内の閉路の存在
- 連結成分内の次数 $3$ 以上の存在

を判定したい。
連結性が必要なので、重み順に辺を追加して部分永続 UnionFind するのが良いだろう。
閉路と次数の条件も、 UnionFind に追加情報を持たせればできる。 (部分永続なので条件を満たした時間)

計算量は $O(M \log (N + M) + Q \log N \log M)$

オンラインでなければ、 Parallel Binary Search で $\log$ が $1$ 個になる。

## 実装

一般的な部分永続 UnionFind では `root` が `t < time` で時刻 $t$ の直後の根を返すのに対し、時刻 $t$ の直後に条件を満たしているかどうか調べるには `time <= t` になる。

https://oj.uz/submission/365005

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

struct UnionFind{
    vector<vector<pair<int, int>>> data;
    vector<int> flag_time, degree;
    UnionFind(int n = 0): data(n, {{-1, -1}}), flag_time(n, INT_MAX), degree(n){}
    int merged_time(int x) const {
        const auto [time, root] = data[x].back();
        if(root < 0) return INT_MAX;
        return time;
    }
    int root(int t, int x) const { // after t
        if(t < merged_time(x)) return x;
        return root(t, data[x].back().second);
    }
    bool unite(int t, int x, int y){
        bool flag = ++degree[x] >= 3 || ++degree[y] >= 3;
        x = root(t, x);
        y = root(t, y);
        if(x == y){
            if(flag_time[x] == INT_MAX) flag_time[x] = t;
            return 0;
        }
        const int size_x = data[x].back().second, size_y = data[y].back().second;
        if(size_x > size_y) swap(x, y);
        if(flag_time[x] == INT_MAX && (flag || flag_time[y] != INT_MAX)) flag_time[x] = t;
        data[x].emplace_back(t, size_x + size_y);
        data[y].emplace_back(t, x);
        return 1;
    }
} uf;
vector<array<int, 3>> edge;

void init(int N, int M, vector<int> U, vector<int> V, vector<int> W){
    uf = UnionFind(N);
    edge.resize(M);
    for(int i = 0; i < M; i++) edge[i] = {U[i], V[i], W[i]};
    sort(edge.begin(), edge.end(), [&](const auto& a, const auto& b){ return a[2] < b[2]; });
    for(int i = 0; i < M; i++){
        const auto& [U, V, W] = edge[i];
        uf.unite(i + 1, U, V);
    }
}

int getMinimumFuelCapacity(int X, int Y){
    auto check = [&](int t){
        const int x = uf.root(t, X), y = uf.root(t, Y);
        return x == y && uf.flag_time[x] <= t;
    };
    int ng = 0, ok = edge.size();
    if(!check(ok)) return -1;
    while(ok - ng > 1){
        const int cen = (ok + ng) / 2;
        (check(cen) ? ok : ng) = cen;
    }
    return edge[ok - 1][2];
}