結果
| 問題 |
No.1950 片道きゃっちぼーる
|
| コンテスト | |
| ユーザー |
 atcoder8
|
| 提出日時 | 2022-09-10 17:04:17 |
| 言語 | Rust (1.83.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 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 13 WA * 10 |
ソースコード
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()
}
}
}
}