結果
問題 | No.2290 UnUnion Find |
ユーザー |
|
提出日時 | 2023-05-05 22:32:27 |
言語 | Rust (1.83.0 + proconio) |
結果 |
TLE
|
実行時間 | - |
コード長 | 7,430 bytes |
コンパイル時間 | 15,207 ms |
コンパイル使用メモリ | 376,860 KB |
実行使用メモリ | 30,380 KB |
最終ジャッジ日時 | 2024-11-23 09:32:31 |
合計ジャッジ時間 | 153,820 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 2 TLE * 44 |
ソースコード
//https://github.com/rust-lang-ja/ac-library-rspub mod dsu {//! A Disjoint set union (DSU) with union by size and path compression./// A Disjoint set union (DSU) with union by size and path compression.////// See: [Zvi Galil and Giuseppe F. Italiano, Data structures and algorithms for disjoint set union problems](https://core.ac.uk/download/pdf/161439519.pdf)////// In the following documentation, let $n$ be the size of the DSU.////// # Example////// ```/// use ac_library_rs::Dsu;/// use proconio::{input, source::once::OnceSource};////// input! {/// from OnceSource::from(/// "5\n\/// 3\n\/// 0 1\n\/// 2 3\n\/// 3 4\n",/// ),/// n: usize,/// abs: [(usize, usize)],/// }////// let mut dsu = Dsu::new(n);/// for (a, b) in abs {/// dsu.merge(a, b);/// }////// assert!(dsu.same(0, 1));/// assert!(!dsu.same(1, 2));/// assert!(dsu.same(2, 4));////// assert_eq!(/// dsu.groups()/// .into_iter()/// .map(|mut group| {/// group.sort_unstable();/// group/// })/// .collect::<Vec<_>>(),/// [&[0, 1][..], &[2, 3, 4][..]],/// );/// ```pub struct Dsu {n: usize,// root node: -1 * component size// otherwise: parentparent_or_size: Vec<i32>,}impl Dsu {/// Creates a new `Dsu`.////// # Constraints////// - $0 \leq n \leq 10^8$////// # Complexity////// - $O(n)$pub fn new(size: usize) -> Self {Self {n: size,parent_or_size: vec![-1; size],}}// `\textsc` does not work in KaTeX/// Performs the Uɴɪᴏɴ operation.////// # Constraints////// - $0 \leq a < n$/// - $0 \leq b < n$////// # Panics////// Panics if the above constraints are not satisfied.////// # Complexity////// - $O(\alpha(n))$ amortizedpub fn merge(&mut self, a: usize, b: usize) -> usize {assert!(a < self.n);assert!(b < self.n);let (mut x, mut y) = (self.leader(a), self.leader(b));if x == y {return x;}if -self.parent_or_size[x] < -self.parent_or_size[y] {std::mem::swap(&mut x, &mut y);}self.parent_or_size[x] += self.parent_or_size[y];self.parent_or_size[y] = x as i32;x}/// Returns whether the vertices $a$ and $b$ are in the same connected component.////// # Constraints////// - $0 \leq a < n$/// - $0 \leq b < n$////// # Panics////// Panics if the above constraint is not satisfied.////// # Complexity////// - $O(\alpha(n))$ amortizedpub fn same(&mut self, a: usize, b: usize) -> bool {assert!(a < self.n);assert!(b < self.n);self.leader(a) == self.leader(b)}/// Performs the Fɪɴᴅ operation.////// # Constraints////// - $0 \leq a < n$////// # Panics////// Panics if the above constraint is not satisfied.////// # Complexity////// - $O(\alpha(n))$ amortizedpub fn leader(&mut self, a: usize) -> usize {assert!(a < self.n);if self.parent_or_size[a] < 0 {return a;}self.parent_or_size[a] = self.leader(self.parent_or_size[a] as usize) as i32;self.parent_or_size[a] as usize}/// Returns the size of the connected component that contains the vertex $a$.////// # Constraints////// - $0 \leq a < n$////// # Panics////// Panics if the above constraint is not satisfied.////// # Complexity////// - $O(\alpha(n))$ amortizedpub fn size(&mut self, a: usize) -> usize {assert!(a < self.n);let x = self.leader(a);-self.parent_or_size[x] as usize}/// Divides the graph into connected components.////// The result may not be ordered.////// # Complexity////// - $O(n)$pub fn groups(&mut self) -> Vec<Vec<usize>> {let mut leader_buf = vec![0; self.n];let mut group_size = vec![0; self.n];for i in 0..self.n {leader_buf[i] = self.leader(i);group_size[leader_buf[i]] += 1;}let mut result = vec![Vec::new(); self.n];for i in 0..self.n {result[i].reserve(group_size[i]);}for i in 0..self.n {result[leader_buf[i]].push(i);}result.into_iter().filter(|x| !x.is_empty()).collect::<Vec<Vec<usize>>>()}}#[cfg(test)]mod tests {use super::*;#[test]fn dsu_works() {let mut d = Dsu::new(4);d.merge(0, 1);assert!(d.same(0, 1));d.merge(1, 2);assert!(d.same(0, 2));assert_eq!(d.size(0), 3);assert!(!d.same(0, 3));assert_eq!(d.groups(), vec![vec![0, 1, 2], vec![3]]);}}}use dsu::*;fn solve(scanner: &mut Scanner) {let n: usize = scanner.next();let q: usize = scanner.next();let mut dsu = Dsu::new(n);for _ in 0..q {let t: usize = scanner.next();if t == 1 {let u: usize = scanner.next();let v: usize = scanner.next();let u = u - 1;let v = v - 1;dsu.merge(u, v);} else {let v: usize = scanner.next();let v = v - 1;let mut ans: isize = -1;for g in dsu.groups() {let u = g[0];if dsu.leader(u) != dsu.leader(v) {ans = (u + 1) as isize;break;}}println!("{}", ans);}}}fn main() {let mut scanner = Scanner::new();let t: usize = 1;for _ in 0..t {solve(&mut scanner);}}pub struct Scanner {buf: Vec<String>,}impl Scanner {fn new() -> Self {Self { buf: vec![] }}fn next<T: std::str::FromStr>(&mut self) -> T {loop {if let Some(x) = self.buf.pop() {return x.parse().ok().expect("");}let mut source = String::new();std::io::stdin().read_line(&mut source).expect("");self.buf = Self::split(source);}}fn split(source: String) -> Vec<String> {source.split_whitespace().rev().map(String::from).collect::<Vec<_>>()}}