AtCoder Beginner Contest 413 G

https://atcoder.jp/contests/abc413/tasks/abc413_g

典型的な分割統治法を使う問題です。障害物がなるべく半数ずつになるように領域を縦か横かで分割して境界を計算して、境界を統合します。各領域の4つの境界は(範囲, グループ番号)のベクトルで表して、統合するときは片方のグループともう片方のグループが同じグループになるかを調べて、各境界をアップデートします。最後に、Sが接する境界とGが接する境界が同じグループかを調べます。

// Big Banned Grid
#![allow(non_snake_case)]

use std::collections::HashMap;


//////////////////// 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()
}


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

use std::cmp::{min, max};

type Node = usize;

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 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 {
        let mut v = v0;
        while self.parents[v] != v {
            v = self.parents[v]
        }
        v
    }
}


//////////////////// Cell ////////////////////

type Point = (usize, usize);
type Range = (usize, usize);
type Boundary = Vec<(Range, usize)>;

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

struct Cell {
    x1: usize,
    x2: usize,
    y1: usize,
    y2: usize,
    left:   Boundary,
    bottom: Boundary,
    right:  Boundary,
    top:    Boundary
}

impl Cell {
    fn new(x1: usize, x2: usize, y1: usize, y2: usize, left: Boundary,
                    bottom: Boundary, right: Boundary, top: Boundary) -> Cell {
        Cell { x1, x2, y1, y2, left, bottom, right, top }
    }
    
    fn create_left_right(x1: usize, x2: usize, y1: usize,
                                y2: usize, obj: Point) -> (Boundary, Boundary) {
        let (x, y) = obj;
        if y == y1 {
            let mut left = vec![];
            if x > x1 {
                left.push(((x1, x), 0))
            }
            if x < x2 - 1 {
                left.push(((x+1, x2), 0))
            }
            let right = vec![((x1, x2), 0)];
            (left, right)
        }
        else if y == y2 - 1 {
            let left = vec![((x1, x2), 0)];
            let mut right = vec![];
            if x > x1 {
                right.push(((x1, x), 0))
            }
            if x < x2 - 1 {
                right.push(((x+1, x2), 0))
            }
            (left, right)
        }
        else {
            let left = vec![((x1, x2), 0)];
            let right = vec![((x1, x2), 0)];
            (left, right)
        }
    }
    
    fn boundaries(&self) -> Vec<&Boundary> {
        vec![&self.left, &self.bottom, &self.right, &self.top]
    }
    
    fn num_groups(&self) -> usize {
        let mut num_g = 0;
        for b in self.boundaries() {
            for &(_, g) in b.iter() {
                num_g = max(num_g, g + 1)
            }
        }
        num_g as usize
    }
    
    fn create_bottom_top(x1: usize, x2: usize, y1: usize,
                            y2: usize, (x, y): Point) -> (Boundary, Boundary) {
        if x == x1 {
            let mut top: Boundary = vec![];
            if y > y1 {
                top.push(((y1, y), 0))
            }
            if y < y2 - 1 {
                top.push(((y+1, y2), 0))
            }
            let bottom = vec![((y1, y2), 0)];
            (bottom, top)
        }
        else if x == x2 - 1 {
            let top: Boundary = vec![((y1, y2), 0)];
            let mut bottom: Boundary = vec![];
            if y > y1 {
                bottom.push(((y1, y), 0))
            }
            if y < y2 - 1 {
                bottom.push(((y+1, y2), 0))
            }
            (bottom, top)
        }
        else {
            let top: Boundary = vec![((y1, y2), 0)];
            let bottom: Boundary = vec![((y1, y2), 0)];
            (bottom, top)
        }
    }
    
    fn divide_objects(x1: usize, x2: usize, y1: usize, y2: usize,
                                        mut objs: Vec<Point>) -> (Cell, Cell) {
        let min_x = objs.iter().map(|pt| pt.0).min().unwrap();
        let max_x = objs.iter().map(|pt| pt.0).max().unwrap();
        let min_y = objs.iter().map(|pt| pt.1).min().unwrap();
        let max_y = objs.iter().map(|pt| pt.1).max().unwrap();
        if max_x - min_x >= max_y - min_y {
            objs.sort_by_key(|obj| obj.0);
            let mid = objs.len() / 2;
            let x = if objs[0].0 == objs[mid].0 {
                objs[mid].0 + 1
            }
            else {
                objs[mid].0
            };
            let objs1: Vec<Point> = objs.iter().cloned().
                                    filter(|obj| obj.0 < x).collect();
            let objs2: Vec<Point> = objs.iter().cloned().
                                    filter(|obj| obj.0 >= x).collect();
            let cell1 = Cell::create(x1, x, y1, y2, objs1);
            let cell2 = Cell::create(x, x2, y1, y2, objs2);
            (cell1, cell2)
        }
        else {
            objs.sort_by_key(|obj| obj.1);
            let mid = objs.len() / 2;
            let y = if objs[0].1 == objs[mid].1 {
                objs[mid].1 + 1
            }
            else {
                objs[mid].1
            };
            let objs1: Vec<Point> = objs.iter().cloned().
                                    filter(|obj| obj.1 < y).collect();
            let objs2: Vec<Point> = objs.iter().cloned().
                                    filter(|obj| obj.1 >= y).collect();
            let cell1 = Cell::create(x1, x2, y1, y, objs1);
            let cell2 = Cell::create(x1, x2, y, y2, objs2);
            (cell1, cell2)
        }
    }
    
    fn create(x1: usize, x2: usize, y1: usize, y2: usize, objs: Vec<Point>) -> Cell {
        if objs.len() == 1 {
            let (x, y) = objs[0];
            if x2 - x1 == 1 {
                if y2 - y1 == 1 {
                    let left: Boundary = vec![];
                    let bottom: Boundary = vec![];
                    let right: Boundary = vec![];
                    let top: Boundary = vec![];
                    Cell { x1, x2, y1, y2, left, bottom, right, top }
                }
                else if y == y1 {
                    let left: Boundary = vec![];
                    let bottom: Boundary = vec![((y1+1, y2), 0)];
                    let right: Boundary = vec![((x1, x2), 0)];
                    let top: Boundary = vec![((y1+1, y2), 0)];
                    Cell { x1, x2, y1, y2, left, bottom, right, top }
                }
                else if y == y2 - 1 {
                    let left = vec![((x1, x2), 0)];
                    let bottom = vec![((y1, y2-1), 0)];
                    let right = vec![];
                    let top = vec![((y1, y2-1), 0)];
                    Cell { x1, x2, y1, y2, left, bottom, right, top }
                }
                else {
                    let left = vec![((x1, x2), 0)];
                    let bottom = vec![((y1, y), 0), ((y+1, y2), 1)];
                    let right = vec![((x1, x2), 1)];
                    let top = vec![((y1, y), 0), ((y+1, y2), 1)];
                    Cell { x1, x2, y1, y2, left, bottom, right, top }
                }
            }
            else if y2 - y1 == 1 {
                if x == x1 {
                    let left = vec![((x1+1, x2), 0)];
                    let bottom = vec![((y1, y2), 0)];
                    let right = vec![((x1+1, x2), 0)];
                    let top = vec![];
                    Cell { x1, x2, y1, y2, left, bottom, right, top }
                }
                else if x == x2 - 1 {
                    let left = vec![((x1, x2-1), 0)];
                    let bottom = vec![];
                    let right = vec![((x1, x2-1), 0)];
                    let top = vec![((y1, y2), 0)];
                    Cell { x1, x2, y1, y2, left, bottom, right, top }
                }
                else {
                    let left = vec![((x1, x), 0), ((x+1, x2), 1)];
                    let bottom = vec![((y1, y2), 1)];
                    let right = vec![((x1, x), 0), ((x+1, x2), 1)];
                    let top = vec![((y1, y2), 0)];
                    Cell { x1, x2, y1, y2, left, bottom, right, top }
                }
            }
            else {
                let (left, right) = Cell::create_left_right(x1, x2,
                                                            y1, y2, objs[0]);
                let (bottom, top) = Cell::create_bottom_top(x1, x2,
                                                            y1, y2, objs[0]);
                Cell { x1, x2, y1, y2, left, bottom, right, top }
            }
        }
        else {
            let (cell1, cell2) = Cell::divide_objects(x1, x2, y1, y2, objs);
            Cell::merge(cell1, cell2)
        }
    }
    
    // 接するグループ同士を同じグループにする（UnionFindを更新する）
    fn merge_core(b1: &Boundary, b2: &Boundary, ng: usize, uf: &mut UnionFind) {
        let mut k: usize = 0;
        let mut l: usize = 0;
        let L1 = b1.len();
        let L2 = b2.len();
        while k < L1 && l < L2 {
            let ((first1, last1), g1) = b1[k];
            let ((first2, last2), g2) = b2[l];
            let first = max(first1, first2);
            let last = min(last1, last2);
            if first < last {
                uf.connect(g1, g2 + ng)
            }
            if last1 <= last2 {
                k += 1
            }
            if last1 >= last2 {
                l += 1
            }
        }
    }
    
    fn is_same_ends(b1: &Boundary, b2: &Boundary) -> bool {
        if b1.is_empty() || b2.is_empty() {
            return false
        }
        
        let pair1 = b1[b1.len()-1];
        let pair2 = b2[0];
        // 同じグループでかつ接している
        pair1.1 == pair2.1 && pair1.0.1 == pair2.0.0
    }
    
    fn merge_each(b1: &Boundary, b2: &Boundary,
                        conv: &Vec<usize>, ng1: usize) -> Boundary {
        let b1 = Cell::convert(b1, conv, 0);
        let b2 = Cell::convert(b2, conv, ng1);
        if Cell::is_same_ends(&b1, &b2) {
            let (rng1, g) = b1[b1.len()-1];
            let (rng2, _) = b2[0];
            let rng = (rng1.0, rng2.1);
            [&b1[..b1.len()-1], &[(rng, g)], &b2[1..]].concat()
        }
        else {
            [b1.as_slice(), b2.as_slice()].concat()
        }
    }
    
    fn convert(b: &Boundary, conv: &Vec<usize>, d: usize) -> Boundary {
        b.iter().map(|&(rng, g)| (rng, conv[g+d])).collect::<Boundary>()
    }
    
    fn merge(c1: Cell, c2: Cell) -> Cell {
        let ng1 = c1.num_groups();
        let ng2 = c2.num_groups();
        let mut uf = UnionFind::new(ng1 + ng2);
        if c1.x2 == c2.x1 {
            Cell::merge_core(&c1.bottom, &c2.top, ng1, &mut uf)
        }
        else {
            Cell::merge_core(&c1.right, &c2.left, ng1, &mut uf)
        }
        
        // 連結成分を集める
        let mut dic: HashMap<usize, Vec<usize>> = HashMap::new();
        for i in 0..ng1+ng2 {
            let r = uf.root(i);
            let e = dic.entry(r).or_insert(vec![]);
            (*e).push(i)
        }
        
        let mut conv: Vec<usize> = vec![0; ng1+ng2];    // group -> new group
        for (i, (_, vs)) in dic.iter().enumerate() {
            for &v in vs.iter() {
                conv[v] = i
            }
        }
        
        if c1.x2 == c2.x1 {
            let left = Cell::merge_each(&c1.left, &c2.left, &conv, ng1);
            let bottom = Cell::convert(&c2.bottom, &conv, ng1);
            let right = Cell::merge_each(&c1.right, &c2.right, &conv, ng1);
            let top = Cell::convert(&c1.top, &conv, 0);
            Cell::new(c1.x1, c2.x2, c1.y1, c2.y2, left, bottom, right, top)
        }
        else {
            let left = Cell::convert(&c1.left, &conv, 0);
            let bottom = Cell::merge_each(&c1.bottom, &c2.bottom, &conv, ng1);
            let right = Cell::convert(&c2.right, &conv, ng1);
            let top = Cell::merge_each(&c1.top, &c2.top, &conv, ng1);
            Cell::new(c1.x1, c2.x2, c1.y1, c2.y2, left, bottom, right, top)
        }
    }
}


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

fn read_input() -> (usize, usize, Vec<Point>) {
    let v: Vec<usize> = read_vec();
    let (H, W, K) = (v[0], v[1], v[2]);
    let objs: Vec<Point> = (0..K).map(|_| read_point()).collect();
    (H, W, objs)
}

fn F(H: usize, W: usize, objs: Vec<Point>) -> bool {
    if objs.is_empty() {
        return true
    }
    
    let c = Cell::create(0, H, 0, W, objs);
    if c.left.is_empty() {
        return false
    }
    let (rng1, g1) = c.left[0];
    if rng1.0 != 0 {
        return false
    }
    if c.right.is_empty() {
        return false
    }
    let (rng2, g2) = c.right[c.right.len()-1];
    if rng2.1 != H {
        return false
    }
    
    g1 == g2
}

fn main() {
    let (H, W, objs) = read_input();
    println!("{}", YesNo(F(H, W, objs)))
}