Submission #1492037

---

Source Code Expand

fn get_line() -> String {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().to_string()
}

fn reads<T>() -> Vec<T>
    where
        T: std::str::FromStr,
        <T as std::str::FromStr>::Err: std::fmt::Debug {
    get_line().split(' ').map(|x| x.parse().unwrap()).collect()
}

fn readln<T>() -> T
    where
        T: std::str::FromStr,
        <T as std::str::FromStr>::Err: std::fmt::Debug {
    get_line().parse().unwrap()
}

struct UFTree {
    roots: Vec<usize>,
    ranks: Vec<usize>,
}

impl UFTree {
    fn new(num: usize) -> UFTree {
        let mut rs = vec![0; num];
        for i in 0..num {
            rs[i] = i;
        }

        UFTree {
            roots: rs,
            ranks: vec![1; num],
        }
    }

    fn find(&mut self, v: usize) -> Option<usize> {
        if self.roots.len() <= v {
            None
        }
        else {
            let vr = self.roots[v];

            if vr == v {
                Some(v)
            }
            else if let Some(r) = self.find(vr) {
                self.roots[v] = r;

                Some(r)
            }
            else {
                None
            }
        }
    }

    fn unite(&mut self, u: usize, v: usize) {
        if let (Some(ur), Some(vr)) = (self.find(u), self.find(v)) {
            if ur == vr {
                return;
            }

            if self.ranks[ur] < self.ranks[vr] {
                self.roots[ur] = vr;
            }
            else {
                self.roots[vr] = ur;

                if self.ranks[ur] == self.ranks[vr] {
                    self.ranks[ur] += 1;
                }
            }
        }
    }

    fn same(&mut self, u: usize, v: usize) -> bool {
        if let (Some(ur), Some(vr)) = (self.find(u), self.find(v)) {
            ur == vr
        }
        else {
            false
        }
    }
}

use std::collections::BinaryHeap;
use std::cmp::Ordering;

#[derive(Clone, Copy, Eq, PartialEq)]
struct E {
    u: usize,
    v: usize,
    cost: u64,
}

impl Ord for E {
    fn cmp(&self, other: &Self) -> Ordering {
        other.cost.cmp(&self.cost)
    }
}

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

fn main() {
    let wh = reads();
    let mut q = BinaryHeap::new();

    for i in 0..wh[0] {
        let x = readln();

        for j in 0..(wh[1] + 1) {
            q.push(E {u: i * (wh[1] + 1) + j, v: (i + 1) * (wh[1] + 1) + j, cost: x});
        }
    }
    for j in 0..wh[1] {
        let x = readln();

        for i in 0..(wh[0] + 1) {
            q.push(E {u: i * (wh[1] + 1) + j, v: i * (wh[1] + 1) + j + 1, cost: x});
        }
    }

    let mut uft = UFTree::new((wh[0] + 1) * (wh[1] + 1));

    let mut res = 0;
    while let Some(e) = q.pop() {
        if !uft.same(e.u, e.v) {
            uft.unite(e.u, e.v);

            res += e.cost;
        }
    }

    println!("{}", res);
}

Submission Info

Judge Result