#796529 (Rust) No.1950 片道きゃっちぼーる

• 問題: No.1950 片道きゃっちぼーる
• ユーザー: atcoder8
• 提出日時: 2022-09-10 17:04:17
• 言語: Rust (1.77.0 + proconio)
• 結果: WA
• 実行時間: -
• コード長: 12,617 bytes
• コンパイル時間: 14,761 ms
• コンパイル使用メモリ: 379,032 KB
• 実行使用メモリ: 25,620 KB
• 最終ジャッジ日時: 2024-11-26 21:44:21
• 合計ジャッジ時間: 22,530 ms
• ジャッジサーバーID （参考情報）: judge2 / judge1

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	1 ms; 5,248 KB
testcase_01	AC	1 ms; 5,248 KB
testcase_02	AC	2 ms; 5,248 KB
testcase_03	AC	412 ms; 9,244 KB
testcase_04	WA	-
testcase_05	AC	2 ms; 5,248 KB
testcase_06	AC	301 ms; 8,864 KB
testcase_07	AC	317 ms; 25,620 KB
testcase_08	WA	-
testcase_09	WA	-
testcase_10	WA	-
testcase_11	AC	287 ms; 9,076 KB
testcase_12	AC	313 ms; 8,952 KB
testcase_13	WA	-
testcase_14	WA	-
testcase_15	WA	-
testcase_16	AC	289 ms; 9,756 KB
testcase_17	AC	1 ms; 5,248 KB
testcase_18	WA	-
testcase_19	WA	-
testcase_20	AC	302 ms; 25,352 KB
testcase_21	AC	290 ms; 8,856 KB
testcase_22	WA	-

ソースコード

use atcoder8_library::union_find::UnionFind;

fn main() {
    let n = {
        let mut line = String::new();
        std::io::stdin().read_line(&mut line).unwrap();
        line.trim().parse::<usize>().unwrap()
    };
    let xx = {
        let mut line = String::new();
        std::io::stdin().read_line(&mut line).unwrap();
        line.split_whitespace()
            .map(|x| x.parse::<usize>().unwrap())
            .collect::<Vec<_>>()
    };
    let aa = {
        let mut line = String::new();
        std::io::stdin().read_line(&mut line).unwrap();
        line.split_whitespace()
            .map(|x| x.parse::<usize>().unwrap())
            .collect::<Vec<_>>()
    };

    let mut uf = UnionFind::new(n);

    for curr_idx in 0..n {
        if xx[curr_idx] >= aa[curr_idx] {
            if let Ok(next_idx) = xx.binary_search(&(xx[curr_idx] - aa[curr_idx])) {
                uf.merge(curr_idx, next_idx);
            }
        }

        if let Ok(next_idx) = xx.binary_search(&(xx[curr_idx] + aa[curr_idx])) {
            uf.merge(curr_idx, next_idx);
        }
    }

    let groups = uf.groups();
    let mut distances = vec![0; n];

    for component in groups.iter() {
        let max_dist = component
            .iter()
            .map(|&idx| xx[idx] + aa[idx])
            .max()
            .unwrap();

        for &idx in component.iter() {
            distances[idx] = max_dist;
        }
    }

    for (&dist, &x) in distances.iter().zip(xx.iter()) {
        println!("{}", dist - x);
    }
}

/// Performs coordinate compression of `seq`.
///
/// The return value is a tuple of `zip` and `unzip`.
/// `zip` is a list of the number of smallest values in the whole sequence for each element.
/// `unzip` is a list of the values that appear in the number sequence in ascending order.
/// The `i`-th element of the original sequence can be restored by `unzip[zip[i]]`.
pub fn coordinate_compression<T>(seq: &Vec<T>) -> (Vec<usize>, Vec<T>)
where
    T: Clone + Ord,
{
    let mut unzip = seq.clone();
    unzip.sort_unstable();
    unzip.dedup();

    let zip: Vec<usize> = seq
        .iter()
        .map(|x| unzip.binary_search(x).unwrap() as usize)
        .collect();

    (zip, unzip)
}

pub mod atcoder8_library {
    pub mod union_find {
        //! Union-Find processes the following queries for an edgeless graph in `O(α(n))` amortized time.
        //! * Add an undirected edge.
        //! * Deciding whether given two vertices are in the same connected component
        //!
        //! When a method is called, route compression is performed as appropriate.

        use std::collections::HashMap;

        /// Union-Find processes the following queries for an edgeless graph in `O(α(n))` amortized time.
        /// * Add an undirected edge.
        /// * Deciding whether given two vertices are in the same connected component
        ///
        /// When a method is called, route compression is performed as appropriate.
        ///
        /// # Examples
        ///
        /// ```
        /// use atcoder8_library::union_find::UnionFind;
        ///
        /// let mut uf = UnionFind::new(3);
        /// assert_eq!(uf.same(0, 2), false);
        /// uf.merge(0, 1);
        /// assert_eq!(uf.same(0, 2), false);
        /// uf.merge(1, 2);
        /// assert_eq!(uf.same(0, 2), true);
        /// ```
        pub struct UnionFind {
            /// For each element, one of the following is stored.
            /// * Size of the connected component to which it belongs; It is expressed by a negative number
            /// (if it is representative of a connected component)
            /// * Index of the element that is its own parent (otherwise)
            parent_or_size: Vec<i32>,

            /// Number of connected components.
            group_num: usize,
        }

        impl UnionFind {
            /// Creates an undirected graph with `n` vertices and 0 edges.
            ///
            /// # Examples
            ///
            /// ```
            /// use atcoder8_library::union_find::UnionFind;
            ///
            /// let mut uf = UnionFind::new(3);
            /// assert_eq!(uf.same(0, 2), false);
            /// uf.merge(0, 1);
            /// assert_eq!(uf.same(0, 2), false);
            /// uf.merge(2, 1);
            /// assert_eq!(uf.same(0, 2), true);
            /// ```
            pub fn new(n: usize) -> Self {
                UnionFind {
                    parent_or_size: vec![-1; n],
                    group_num: n,
                }
            }

            /// Returns the representative of the connected component that contains the vertex `a`.
            ///
            /// # Examples
            ///
            /// ```
            /// use atcoder8_library::union_find::UnionFind;
            ///
            /// let mut uf = UnionFind::new(3);
            /// uf.merge(1, 2);
            /// assert_eq!(uf.leader(0), 0);
            /// assert_eq!(uf.leader(1), uf.leader(2));
            /// ```
            pub fn leader(&mut self, a: usize) -> usize {
                // Path from A to just before the representative
                // of the connected component to which A belongs
                // (If the representative is A, then it is empty)
                let mut path = vec![];

                // Variable representing the current vertex (initialized with a)
                let mut curr = a;

                // Loop until the vertex indicated by curr becomes the parent.
                while self.parent_or_size[curr] >= 0 {
                    // Add curr to the path.
                    path.push(curr);
                    // Move to parent vertex.
                    curr = self.parent_or_size[curr] as usize;
                }

                // Set the parent of every vertex in the path to representative of the connected component.
                path.iter()
                    .for_each(|&x| self.parent_or_size[x] = curr as i32);

                // Return a representative of the connected component.
                curr
            }

            /// Returns whether the vertices `a` and `b` are in the same connected component.
            ///
            /// # Examples
            ///
            /// ```
            /// use atcoder8_library::union_find::UnionFind;
            ///
            /// let mut uf = UnionFind::new(3);
            /// assert_eq!(uf.same(0, 2), false);
            /// uf.merge(0, 1);
            /// assert_eq!(uf.same(0, 2), false);
            /// uf.merge(2, 1);
            /// assert_eq!(uf.same(0, 2), true);
            /// ```
            pub fn same(&mut self, a: usize, b: usize) -> bool {
                self.leader(a) == self.leader(b)
            }

            /// Adds an edge between vertex `a` and vertex `b`.
            /// Returns true if the connected component to which a belongs and that of b are newly combined.
            ///
            /// # Examples
            ///
            /// ```
            /// use atcoder8_library::union_find::UnionFind;
            ///
            /// let mut uf = UnionFind::new(3);
            /// assert_eq!(uf.same(0, 2), false);
            /// uf.merge(0, 1);
            /// assert_eq!(uf.same(0, 2), false);
            /// uf.merge(2, 1);
            /// assert_eq!(uf.same(0, 2), true);
            /// ```
            pub fn merge(&mut self, a: usize, b: usize) -> bool {
                // Representative of the connected component that contains the vertex a
                let mut leader_a = self.leader(a);
                // Representative of the connected component that contains the vertex b
                let mut leader_b = self.leader(b);

                // If a and b belong to the same connected component, return false without processing.
                if leader_a == leader_b {
                    return false;
                }

                // If the size of the connected component to which a belongs is
                // smaller than that of b, swap a and b.
                if -self.parent_or_size[leader_a] < -self.parent_or_size[leader_b] {
                    std::mem::swap(&mut leader_a, &mut leader_b);
                }

                // Add that of b to the number of elements of the connected component to which a belongs.
                self.parent_or_size[leader_a] += self.parent_or_size[leader_b];

                // Set the parent of the representative of the connected component to which b belongs
                // to the representative of the connected component to which a belongs.
                self.parent_or_size[leader_b] = leader_a as i32;

                // Decrease the number of connected components by one.
                self.group_num -= 1;

                // Return true because the connected component is newly combined.
                true
            }

            /// Returns a list of connected components.
            ///
            /// Each list consists of the indexes of the vertices
            /// of the corresponding connected component.
            /// The lists are arranged in ascending order with respect to
            /// the smallest index contained in the list.
            /// The indexes contained in each list are arranged in ascending order.
            ///
            /// # Examples
            ///
            /// ```
            /// use atcoder8_library::union_find::UnionFind;
            ///
            /// let mut uf = UnionFind::new(5);
            /// uf.merge(1, 2);
            /// uf.merge(2, 3);
            /// assert_eq!(uf.groups(), vec![vec![0], vec![1, 2, 3], vec![4]]);
            /// ```
            pub fn groups(&mut self) -> Vec<Vec<usize>> {
                let mut leader_to_idx: HashMap<usize, usize> = HashMap::new();
                let mut groups: Vec<Vec<usize>> = vec![];

                for i in 0..self.parent_or_size.len() {
                    let leader = self.leader(i);

                    if let Some(&idx) = leader_to_idx.get(&leader) {
                        groups[idx].push(i);
                    } else {
                        leader_to_idx.insert(groups.len(), leader);
                        groups.push(vec![i]);
                    }
                }

                groups
            }

            /// Returns the size of the connected component that contains the vertex `a`.
            ///
            /// # Examples
            ///
            /// ```
            /// use atcoder8_library::union_find::UnionFind;
            ///
            /// let mut uf = UnionFind::new(3);
            /// assert_eq!(uf.size(0), 1);
            /// uf.merge(0, 1);
            /// assert_eq!(uf.size(0), 2);
            /// uf.merge(2, 1);
            /// assert_eq!(uf.size(0), 3);
            /// ```
            pub fn size(&mut self, a: usize) -> usize {
                let leader = self.leader(a);
                -self.parent_or_size[leader] as usize
            }

            /// Adds a new vertex.
            ///
            /// # Examples
            ///
            /// ```
            /// use atcoder8_library::union_find::UnionFind;
            ///
            /// let mut uf = UnionFind::new(4);
            /// uf.merge(1, 2);
            /// uf.merge(2, 3);
            /// assert_eq!(uf.groups(), vec![vec![0], vec![1, 2, 3]]);
            /// uf.add();
            /// assert_eq!(uf.groups(), vec![vec![0], vec![1, 2, 3], vec![4]]);
            /// ```
            pub fn add(&mut self) {
                self.parent_or_size.push(-1);
                self.group_num += 1;
            }

            /// Returns the number of connected components.
            ///
            /// # Examples
            ///
            /// ```
            /// use atcoder8_library::union_find::UnionFind;
            ///
            /// let mut uf = UnionFind::new(3);
            /// assert_eq!(uf.group_num(), 3);
            /// uf.merge(0, 1);
            /// assert_eq!(uf.group_num(), 2);
            /// uf.merge(2, 1);
            /// assert_eq!(uf.group_num(), 1);
            /// ```
            pub fn group_num(&self) -> usize {
                self.group_num
            }

            /// Returns the number of elements.
            ///
            /// # Examples
            ///
            /// ```
            /// use atcoder8_library::union_find::UnionFind;
            ///
            /// let mut uf = UnionFind::new(5);
            /// assert_eq!(uf.elem_num(), 5);
            /// ```
            pub fn elem_num(&self) -> usize {
                self.parent_or_size.len()
            }
        }
    }
}