Submission #1290428

---

Source Code Expand

#[macro_use]
#[allow(unused)]
mod io {
    use std::io::*;

    pub trait Scan<T> {
        fn scan<R: Read>(sc: &mut Scanner<R>) -> T;
    }

    macro_rules! scan_primitive {
        ($t: ty) => {
            impl Scan<$t> for $t {
                fn scan<R: Read>(sc: &mut Scanner<R>) -> $t {
                    sc.next_token().expect("EOF?").parse()
                        .unwrap_or_else(|e| panic!("Cannot parse {}", e))
                }
            }
        };
        ($t: ty, $($u: ty),+) => {
            scan_primitive!($t);
            scan_primitive!($($u),+);
        };
    }

    macro_rules! scan_tuple {
        ($($t: ident),*) => {
            impl< $($t: Scan<$t>),* > Scan< ( $($t),* ) > for ( $($t),* ) {
                fn scan<R: Read>(sc: &mut Scanner<R>) -> ( $($t),* ) {
                    ( $( $t::scan(sc)),* )
                }
            }
        };
    }

    scan_primitive!(u8, u16, u32, u64, i8, i16, i32, i64,
                    f32, f64, usize, isize, bool, String);
    scan_tuple!(T, U);
    scan_tuple!(T, U, V);
    scan_tuple!(T, U, V, W);

    #[allow(dead_code)]
    pub fn cin() -> Scanner<Stdin> {
        Scanner::new(stdin())
    }

    #[allow(dead_code)]
    pub struct Scanner<T> {
        buf: Vec<u8>,
        len: usize,
        idx: usize,
        reader: T,
    }

    #[allow(dead_code)]
    impl<Reader: Read> Scanner<Reader> {
        pub fn new(r: Reader) -> Scanner<Reader> {
            Scanner {
                buf: vec![0; 8192],
                len: 0,
                idx: 0,
                reader: r,
            }
        }

        pub fn next<T: Scan<T>>(&mut self) -> T {
            T::scan::<Reader>(self)
        }

        fn next_token(&mut self) -> Option<String> {
            let mut res = String::with_capacity(16);
            while let Some(c) = self.get_u8() {
                let d = c as char;
                if !d.is_whitespace() {
                    res.push(d);
                } else if res.len() != 0 {
                    self.unget_u8(c);
                    break;
                }
            }
            if res.len() == 0 { None } else { Some(res) }
        }

        pub fn next_line(&mut self) -> String {
            self.next_line_wrapped().unwrap()
        }

        pub fn next_line_wrapped(&mut self) -> Option<String> {
            let c = self.get_u8();
            if c.is_none() {
                return None;
            }
            let mut line = String::with_capacity(20);
            line.push(c.unwrap() as char);
            loop {
                let c = self.get_u8();
                if c.is_none() || c.unwrap() == b'\n' {
                    // コメントはC++等での仕様
                    // if c.is_some() {
                    //     self.unget_u8(b'\n');
                    // }
                    return Some(line);
                }
                line.push(c.unwrap() as char);
            }
        }

        pub fn has_next(&mut self) -> bool {
            loop {
                let c = self.get_u8();
                if c.is_none() {
                    return false;
                }
                let c = c.unwrap();
                if !(c as char).is_whitespace() {
                    self.unget_u8(c);
                    return true;
                }
            }
        }

        fn get_u8(&mut self) -> Option<u8> {
            if self.idx == self.len {
                match self.reader.read(&mut self.buf[..]) {
                    Ok(l) if l > 0 => {
                        self.idx = 0;
                        self.len = l;
                    }
                    _ => return None,
                }
            }
            self.idx += 1;
            Some(self.buf[self.idx - 1])
        }

        fn unget_u8(&mut self, c: u8) {
            self.idx = self.idx - 1;
            self.buf[self.idx] = c;
        }
    }

    // Output
    macro_rules! dump {
        ($($a: expr),+) => {{
            use std::io::*;
            write!(stderr(), "{}:{}\t", file!(), line!()).unwrap();
            dump!(A $($a),+);
            write!(stderr(), " = ").unwrap();
            dump!(B $($a),+);
            writeln!(stderr(), "").unwrap();
        }};
        (A $x: expr) => {
            write!(stderr(), "{}", stringify!($x)).unwrap();
        };
        (A $x: expr, $($y: expr),+) => {
            write!(stderr(), "{}, ", stringify!($x)).unwrap();
            dump!(A $($y),+);
        };
        (B $x: expr) => {
            write!(stderr(), "{:?}", $x).unwrap();
        };
        (B $x: expr, $($y: expr),+) => {
            write!(stderr(), "{:?}, ", $x).unwrap();
            dump!(B $($y),+);
        };
    }

    macro_rules! p {
        ($x:expr) => {
            println!("{:.10}", $x);
        };
        ($x:expr, $($y:expr),+) => {
            print!("{:.10} ", $x);
            p!($($y),+);
        };
    }
}

#[allow(dead_code)]
struct UnionFind {
    par: Vec<i32>,
    sz: usize,
}

#[allow(dead_code)]
impl UnionFind {
    fn new(n: usize) -> UnionFind {
        UnionFind {
            par: vec![-1; n],
            sz: n,
        }
    }

    fn find(&mut self, a: usize) -> usize {
        if self.par[a] < 0 {
            a
        } else {
            let t = self.par[a];
            self.par[a] = self.find(t as usize) as i32;
            self.par[a] as usize
        }
    }

    fn merge(&mut self, a: usize, b: usize) -> bool {
        let a = self.find(a);
        let b = self.find(b);
        if a == b {
            false
        } else {
            let (a, b) = if self.par[a] > self.par[b] {
                (b, a)
            } else {
                (a, b)
            };
            self.par[a] += self.par[b];
            self.par[b] = a as i32;
            self.sz -= 1;
            true
        }
    }

    fn same(&mut self, a: usize, b: usize) -> bool {
        self.find(a) == self.find(b)
    }

    fn size(&mut self, a: usize) -> usize {
        let a = self.find(a);
        -self.par[a] as usize
    }

    fn num_groups(&self) -> usize {
        self.sz
    }
}

fn main() {
    use io::*;
    let mut sc = cin();
    let (n, q) = sc.next();
    let mut uf = UnionFind::new(n);
    for _ in 0..q {
        let (p, a, b):(u32, _, _) = sc.next();
        if p == 0 {
            uf.merge(a, b);
        } else {
            p!(if uf.same(a, b) { "Yes" } else { "No" });
        }
    }
}

Submission Info

Judge Result