AtCoder Beginner Contest 409 F

https://atcoder.jp/contests/abc409/tasks/abc409_f

1500点しかないので、全ての点の距離を調べることができて、それをPriorityQueueに入れれば近い順に取り出すことができます。点を追加したら今までの点との距離を計算してPriorityQueueに入れます。マージはPriorityQueueから2点を取り出して、連結でない最も近い2点を取り出してUnion-Findでマージします。

// Connecting Points
#![allow(non_snake_case)]


//////////////////// library ////////////////////

fn read<T: std::str::FromStr>() -> T {
    let mut line = String::new();
    std::io::stdin().read_line(&mut line).ok();
    line.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>().split_whitespace()
            .map(|e| e.parse().ok().unwrap()).collect()
}

fn YesNo(b: bool) -> String {
    return if b { "Yes" } else { "No" }.to_string()
}


//////////////////// Edge ////////////////////

use std::collections::BinaryHeap;

type Node = usize;
type Point = (i32, i32);
type Dist = i32;

fn read_point() -> Point {
    let v: Vec<i32> = read_vec();
    (v[0], v[1])
}

#[derive(Debug, Eq, PartialEq, Copy, Clone)]
struct Edge {
    u: Node,
    v: Node,
    dist: Dist,
}

impl Edge {
    fn distance(pt1: Point, pt2: Point) -> Dist {
        (pt1.0 - pt2.0).abs() + (pt1.1 - pt2.1).abs()
    }
    
    fn create(u: Node, v: Node, pts: &Vec<Point>) -> Edge {
        Edge { u, v, dist: Edge::distance(pts[u], pts[v]) }
    }
}

impl Ord for Edge {
    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
        other.dist.cmp(&self.dist)
    }
}

impl PartialOrd for Edge {
    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
        Some(self.cmp(other))
    }
}


//////////////////// UnionFind ////////////////////

use std::cmp::max;

struct UnionFind {
    parents: Vec<Node>,
    heights: Vec<i32>,
}

impl UnionFind {
    fn new(N: usize) -> UnionFind {
        let parents: Vec<Node> = (0..N).collect();
        let heights: Vec<i32> = vec![1; N];
        UnionFind { parents, heights }
    }
    
    fn is_root(&self, v: Node) -> bool {
        self.parents[v] == v
    }
    
    fn is_connected(&self, u: Node, v: Node) -> bool {
        self.root(u) == self.root(v)
    }
    
    fn connect(&mut self, u: Node, v: Node) {
        let r1 = self.root(u);
        let r2 = self.root(v);
        if r1 == r2 {
            return
        }
        
        let h1 = self.heights[r1];
        let h2 = self.heights[r2];
        if h1 <= h2 {   // r2にr1がぶら下がる
            self.parents[r1] = r2;
            self.heights[r2] = max(self.heights[r2], self.heights[r1]+1);
        }
        else {
            self.parents[r2] = r1;
            self.heights[r1] = max(self.heights[r1], self.heights[r2]+1);
        }
    }
    
    fn root(&self, v0: Node) -> Node {
        if self.is_root(v0) {
            v0
        }
        else {
            let p = self.parents[v0];
            self.root(p)
        }
    }
    
    fn add(&mut self) {
        self.parents.push(self.parents.len());
        self.heights.push(1)
    }
}


//////////////////// Graph ////////////////////

struct Graph {
    points: Vec<Point>,
    uf: UnionFind,
    heap: BinaryHeap<Edge>
}

impl Graph {
    fn Add(&mut self, pt: Point) {
        self.points.push(pt);
        self.uf.add();
        let N = self.points.len();
        for u in 0..N-1 {
            self.heap.push(Edge::create(u, N-1, &self.points))
        }
    }
    
    fn Merge(&mut self) {
        // 最小距離のエッジを取り出す
        // まず連結でないエッジを探す
        let mut edges: Vec<Edge> = vec![];
        while let Some(edge) = self.heap.pop() {
            if !self.uf.is_connected(edge.u, edge.v) {
                edges.push(edge);
                break
            }
        }
        if edges.is_empty() {
            println!("-1");
            return
        }
        
        let k = edges[0].dist;
        while let Some(&ref edge) = self.heap.peek() {
            if edge.dist != k {
                break
            }
            // 連結でもよい
            edges.push(self.heap.pop().unwrap())
        }
        
        for edge in edges {
            self.uf.connect(edge.u, edge.v)
        }
        println!("{}", k)
    }
    
    fn Out(&self, u: Node, v: Node) {
        println!("{}", YesNo(self.uf.is_connected(u, v)))
    }
    
    fn create_heap(points: &Vec<Point>) -> BinaryHeap<Edge> {
        let N = points.len();
        let mut heap = BinaryHeap::new();
        for u in 0..N {
            for v in u+1..N {
                heap.push(Edge::create(u, v, points))
            }
        }
        heap
    }
    
    fn create(points: Vec<Point>) -> Graph {
        let N = points.len();
        let uf = UnionFind::new(N);
        let heap = Graph::create_heap(&points);
        Graph { points, uf, heap }
    }
}


//////////////////// Query ////////////////////

enum Query {
    Add(i32, i32),
    Merge(),
    Out(usize, usize),
}

impl Query {
    fn read() -> Query {
        let v: Vec<usize> = read_vec();
        if v[0] == 1 {
            Query::Add(v[1] as i32, v[2] as i32)
        }
        else if v[0] == 2 {
            Query::Merge()
        }
        else {
            Query::Out(v[1]-1, v[2]-1)
        }
    }
}

fn query(q: Query, graph: &mut Graph) {
    match q {
        Query::Add(x, y) => graph.Add((x, y)),
        Query::Merge()   => graph.Merge(),
        Query::Out(u, v) => graph.Out(u, v)
    }
}


//////////////////// process ////////////////////

fn read_input() -> (usize, Vec<Point>) {
    let v: Vec<usize> = read_vec();
    let (N, Q) = (v[0], v[1]);
    let pts: Vec<Point> = (0..N).map(|_| read_point()).collect();
    (Q, pts)
}

fn F(Q: usize, points: Vec<Point>) {
    let mut graph = Graph::create(points);
    for _ in 0..Q {
        let q = Query::read();
        query(q, &mut graph)
    }
}

fn main() {
    let (Q, points) = read_input();
    F(Q, points)
}