Submission #1125063

---

Source Code Expand

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

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

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

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

    fn next<T: std::str::FromStr>(&mut self) -> T {
        self.wrapped::<T>().unwrap()
    }

    fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
        (0..n).map(|_| self.next()).collect()
    }

    fn mat<T: std::str::FromStr>(&mut self, r: usize, c: usize) -> Vec<Vec<T>> {
        (0..r).map(|_| self.vec(c)).collect()
    }

    fn vec_char(&mut self) -> Vec<char> {
        self.read();
        self.next.take().unwrap().chars().collect()
    }

    fn mat_char(&mut self, r: usize) -> Vec<Vec<char>> {
        (0..r).map(|_| self.vec_char()).collect()
    }

    fn wrapped<T: std::str::FromStr>(&mut self) -> Option<T> {
        self.read();
        self.next.take().and_then(|s| s.parse::<T>().ok())
    }

    fn read(&mut self) -> bool {
        if self.next.is_some() {
            return true;
        }
        let mut s = String::with_capacity(16);
        while let Some(c) = self.get_char() {
            if !c.is_whitespace() {
                s.push(c);
            } else if !s.is_empty() {
                break;
            }
        }
        self.next = if !s.is_empty() { Some(s) } else { None };
        self.next.is_some()
    }

    fn get_char(&mut self) -> Option<char> {
        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] as char)
    }
}

#[allow(dead_code)]
struct Xor128 {
    x: u32, y: u32, z: u32, w: u32,
}

#[allow(dead_code)]
impl Xor128 {
    fn new() -> Xor128 {
        use std::io::Read;
        let mut buf = [0; 4];
        let mut urand = std::fs::File::open("/dev/urandom").unwrap();
        urand.read(&mut buf).unwrap();
        let mut seed: u32 = 0;
        seed |= (buf[0] as u32) << 0;
        seed |= (buf[1] as u32) << 8;
        seed |= (buf[2] as u32) << 16;
        seed |= (buf[3] as u32) << 24;
        Xor128::from_seed(seed)
    }

    fn from_seed(seed: u32) -> Xor128 {
        let mut res = Xor128 { x: 123456789, y: 987654321, z:1000000007, w: seed };
        for _ in 0..10 { res.gen(); };
        res
    }

    fn gen(&mut self) -> u32 {
        let t = self.x ^ (self.x << 11);
        self.x = self.y;
        self.y = self.z;
        self.z = self.w;
        self.w = (self.w ^ (self.w >> 19)) ^ (t ^ (t >> 8));
        self.w
    }

    fn next(&mut self, right: u32) -> u32 {
        self.gen() % right
    }

    fn next_in(&mut self, left: i32, right: i32) -> i32 {
        left + self.next((right - left + 1) as u32) as i32
    }

    fn sample<'a, T>(&mut self, values: &'a [T]) -> Option<&'a T> where Self: Sized {
        if values.is_empty() {
            None
        } else {
            Some(&values[self.next(values.len() as u32) as usize])
        }
    }

    fn sample_mut<'a, T>(&mut self, values: &'a mut [T]) -> Option<&'a mut T> where Self: Sized {
        if values.is_empty() {
            None
        } else {
            Some(&mut values[self.next(values.len() as u32) as usize])
        }
    }

    fn shuffle<T>(&mut self, values: &mut [T]) where Self: Sized {
        let mut i = values.len();
        while i >= 2 {
            values.swap(i, self.next(i as u32) as usize);
            i -= 1;
        }
    }
}

#[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 mut a = self.find(a);
        let mut b = self.find(b);
        if a == b {
            false
        } else {
            if self.par[a] > self.par[b] {
                std::mem::swap(&mut a, &mut 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 i32)) as usize
    }
}

#[allow(dead_code)]
struct Chrono {
    st: std::time::SystemTime
}

#[allow(dead_code)]
impl Chrono {
    fn new() -> Chrono {
        Chrono {
            st: std::time::SystemTime::now()
        }
    }
    fn elapsed_ms(&self) -> u64 {
        let elapsed = self.st.elapsed().unwrap();
        elapsed.as_secs()*1000 + elapsed.subsec_nanos() as u64 / 1000000
    }
    fn reset(&mut self) {
        self.st = std::time::SystemTime::now();
    }
}

Submission Info

Judge Result