Submission #2554658


Source Code Expand

macro_rules! semigroup_impl {
  ($marker:ty, $t:ty, | $lhs:ident, $rhs:ident | $append:expr) => {
    impl $crate::math::algebra::Semigroup for $marker {
      type T = $t;

      fn append($lhs: &$t, $rhs: &$t) -> $t {
        $append
      }
    }
  };
}

macro_rules! monoid_impl {
  ($marker:ty, $t:ty, | $lhs:ident, $rhs:ident | $append:expr, $identity:expr) => {
    semigroup_impl! { $marker, $t, |$lhs, $rhs| $append }

    impl $crate::math::algebra::Monoid for $marker {
      fn identity() -> $t {
        $identity
      }
    }
  };
}

macro_rules! group_impl {
  ($marker:ty, $t:ty, | $lhs:ident, $rhs:ident | $append:expr, | $x:ident | $invert:expr, $identity:expr) => {
    monoid_impl! { $marker, $t, |$lhs, $rhs| $append, $identity }

    impl $crate::math::algebra::Group for $marker {
      fn invert($x: &$t) -> $t {
        $invert
      }
    }
  };
}

macro_rules! commutative_monoid_impl {
  ($marker:ty, $t:ty, | $lhs:ident, $rhs:ident | $append:expr, $identity:expr) => {
    monoid_impl! { $marker, $t, |$lhs, $rhs| $append, $identity }

    impl $crate::math::algebra::CommutativeMonoid for $marker {}
  };
}

macro_rules! commutative_group_impl {
  ($marker:ty, $t:ty, | $lhs:ident, $rhs:ident | $append:expr, | $x:ident | $invert:expr, $identity:expr) => {
    group_impl! { $marker, $t, |$lhs, $rhs| $append, |$x| $invert, $identity }

    impl $crate::math::algebra::CommutativeMonoid for $marker {}

    impl $crate::math::algebra::CommutativeGroup for $marker {}
  };
}

fn solve<R: BufRead, W: Write>(_reader: R, _writer: &mut W) {
  let mut _scanner = Scanner::new(_reader);
  #[allow(unused_macros)]
  macro_rules! scan {
    ($t:ty) => { _scanner.next::<$t>() };
    ($($t:ty),+) => { ($(scan!($t)),+) };
    ($t:ty; $n:expr) => {{
      let mut vec = Vec::with_capacity($n);
      for _ in 0..$n {
        vec.push(scan!($t));
      }
      vec
    }};
    ($t_0:ty, $t_1:ty; $n:expr) => { scan!($t_0 = 0, $t_1 = 1; $n) };
    ($t_0:ty, $t_1:ty, $t_2:ty; $n:expr) => { scan!($t_0 = 0, $t_1 = 1, $t_2 = 2; $n) };
    ($($t:ty = $i:tt),+; $n:expr) => {{
      let mut vecs = ($(Vec::<$t>::with_capacity($n)),+);
      for _ in 0..$n {$(
        vecs.$i.push(scan!($t));
      )+}
      vecs
    }};
  }
  #[allow(unused_macros)]
  macro_rules! println {
    () => { writeln!(_writer).unwrap() };
    ($fmt:expr) => { writeln!(_writer, $fmt).unwrap() };
    ($fmt:expr, $($arg:tt)*) => { writeln!(_writer, $fmt, $($arg)*).unwrap() };
  }

  use data_structures::PotentializedUnionFindTree;

  struct UnitGroup;
  commutative_group_impl! { UnitGroup, (), |_l, _r| (), |_x| (), () }

  pub struct UnionFindTree {
    uf: PotentializedUnionFindTree<UnitGroup>,
  }

  impl UnionFindTree {
    pub fn new(size: usize) -> Self {
      UnionFindTree { uf: PotentializedUnionFindTree::new(size) }
    }

    pub fn unite(&mut self, l_index: usize, r_index: usize) -> bool {
      self.uf.unite(l_index, r_index, &())
    }

    pub fn is_same_group(&mut self, l_index: usize, r_index: usize) -> bool {
      self.uf.is_same_group(l_index, r_index)
    }
  }

  let (n, q) = scan!(usize, usize);
  let mut uf = UnionFindTree::new(n);
  for _ in 0..q {
    let (p, a, b) = scan!(usize, usize, usize);
    match p {
      0 => {
        uf.unite(a, b);
      }
      1 => {
        let ans = if uf.is_same_group(a, b) { "Yes" } else { "No" };
        println!("{}", ans);
      }
      _ => unreachable!(),
    }
  }
}

fn main() {
  let stdin = stdin();
  let stdout = stdout();
  #[cfg(debug_assertions)]
  let mut writer = stdout.lock();
  #[cfg(not(debug_assertions))]
  let mut writer = ::std::io::BufWriter::new(stdout.lock());
  solve(stdin.lock(), &mut writer);
  writer.flush().unwrap();
}

use io::Scanner;
use std::io::{stdin, stdout, BufRead, Write};

pub mod math {
  pub mod algebra {
    pub use self::commutative_group::*;
    pub use self::commutative_monoid::*;
    pub use self::group::*;
    pub use self::monoid::*;
    pub use self::semigroup::*;

    mod semigroup {
      use std::fmt::Debug;

      pub trait Semigroup {
        type T: Clone + PartialEq + Debug;

        fn append(lhs: &Self::T, rhs: &Self::T) -> Self::T;

        fn append_assign(lhs: &mut Self::T, rhs: &Self::T) {
          *lhs = Self::append(lhs, rhs);
        }
      }
    }

    mod monoid {
      use math::algebra::Semigroup;

      pub trait Monoid: Semigroup {
        fn identity() -> Self::T;
      }
    }

    mod group {
      use math::algebra::Monoid;

      pub trait Group: Monoid {
        fn invert(&Self::T) -> Self::T;

        fn append_inverse(lhs: &Self::T, rhs: &Self::T) -> Self::T {
          Self::append(lhs, &Self::invert(rhs))
        }

        fn append_inverse_assign(lhs: &mut Self::T, rhs: &Self::T) {
          *lhs = Self::append_inverse(lhs, rhs);
        }
      }
    }

    mod commutative_monoid {
      use math::algebra::Monoid;

      pub trait CommutativeMonoid: Monoid {}
    }

    mod commutative_group {
      use math::algebra::{CommutativeMonoid, Group};

      pub trait CommutativeGroup: Group + CommutativeMonoid {}
    }
  }
}

pub mod data_structures {
  pub use self::potentialized_union_find_tree::*;

  mod potentialized_union_find_tree {
    use math::algebra::CommutativeGroup;
    use std::mem::swap;

    pub struct PotentializedUnionFindTree<G: CommutativeGroup> {
      nodes: Vec<PotentializedNode<G>>,
    }

    #[derive(Clone, Copy)]
    enum Node {
      Root { node_count: usize },
      Descendant { parent_index: usize },
    }

    struct PotentializedNode<G: CommutativeGroup> {
      node: Node,
      potential: G::T,
    }

    impl<G: CommutativeGroup> Clone for PotentializedNode<G> {
      fn clone(&self) -> Self {
        PotentializedNode { potential: self.potential.clone(), ..*self }
      }
    }

    impl<G: CommutativeGroup> PotentializedUnionFindTree<G> {
      pub fn new(size: usize) -> Self {
        PotentializedUnionFindTree {
          nodes: vec![
            PotentializedNode {
              node: Node::Root { node_count: 1 },
              potential: G::identity(),
            };
            size
          ],
        }
      }

      pub fn len(&self) -> usize {
        self.nodes.len()
      }

      pub fn unite(&mut self, l_index: usize, r_index: usize, potential_diff: &G::T) -> bool {
        debug_assert!(l_index < self.len());
        debug_assert!(r_index < self.len());
        let mut l_root_index = self.find(l_index);
        let mut r_root_index = self.find(r_index);
        if l_root_index == r_root_index {
          return false;
        }
        let l_potential = self.potential_diff(l_root_index, l_index).unwrap();
        let r_potential = self.potential_diff(r_root_index, r_index).unwrap();
        let mut potential_diff = G::append_inverse(&G::append(potential_diff, &l_potential), &r_potential);
        match (self.nodes[l_root_index].node, self.nodes[r_root_index].node) {
          (Node::Root { node_count: l_node_count }, Node::Root { node_count: r_node_count }) => {
            let node_count = l_node_count + r_node_count;
            if l_node_count < r_node_count {
              swap(&mut l_root_index, &mut r_root_index);
              potential_diff = G::invert(&potential_diff);
            }
            self.nodes[l_root_index] = PotentializedNode {
              node: Node::Root { node_count: node_count },
              potential: {
                debug_assert_eq!(self.nodes[l_root_index].potential.clone(), G::identity());
                G::identity()
              },
            };
            self.nodes[r_root_index] = PotentializedNode {
              node: Node::Descendant { parent_index: l_root_index },
              potential: potential_diff,
            };
          }
          _ => unreachable!("`find` must return root index"),
        }
        true
      }

      pub fn find(&mut self, index: usize) -> usize {
        debug_assert!(index < self.len());
        match self.nodes[index].node {
          Node::Root { .. } => index,
          Node::Descendant { parent_index } => {
            let root_index = self.find(parent_index);
            debug_assert!(match self.nodes[parent_index].node {
              Node::Root { .. } => true,
              Node::Descendant { parent_index: parent_parent_index } => match self.nodes[parent_parent_index].node {
                Node::Root { .. } => true,
                Node::Descendant { .. } => false,
              },
            });
            self.nodes[index] = PotentializedNode {
              node: Node::Descendant { parent_index: root_index },
              potential: G::append(&self.nodes[parent_index].potential, &self.nodes[index].potential),
            };
            root_index
          }
        }
      }

      pub fn is_same_group(&mut self, l_index: usize, r_index: usize) -> bool {
        debug_assert!(l_index < self.len());
        debug_assert!(r_index < self.len());
        self.find(l_index) == self.find(r_index)
      }

      pub fn count_elements(&mut self, index: usize) -> usize {
        debug_assert!(index < self.len());
        let root_index = self.find(index);
        match self.nodes[root_index].node {
          Node::Root { node_count } => node_count,
          _ => unreachable!("`find` must return root index"),
        }
      }

      pub fn potential_diff(&mut self, l_index: usize, r_index: usize) -> Option<G::T> {
        debug_assert!(l_index < self.len());
        debug_assert!(r_index < self.len());
        if self.is_same_group(l_index, r_index) {
          Some(G::append_inverse(&self.nodes[r_index].potential, &self.nodes[l_index].potential))
        } else {
          None
        }
      }
    }
  }
}

pub mod io {
  pub use self::scanner::*;

  mod scanner {
    use std::fmt::Debug;
    use std::io::BufRead;
    use std::str::{from_utf8, FromStr};

    pub struct Scanner<R> {
      reader: R,
      buffer: Vec<u8>,
      position: usize,
    }

    impl<R: BufRead> Scanner<R> {
      pub fn new(reader: R) -> Self {
        Scanner { reader: reader, buffer: vec![], position: 0 }
      }

      pub fn next<T: FromStr>(&mut self) -> T
      where
        T::Err: Debug,
      {
        from_utf8(self.next_bytes()).unwrap().parse().unwrap()
      }

      pub fn next_bytes(&mut self) -> &[u8] {
        if self.buffer.is_empty() {
          self.read_line();
        }
        loop {
          match self.buffer.get(self.position) {
            Some(&b' ') => self.position += 1,
            Some(&b'\n') => self.read_line(),
            Some(_) => break,
            None => panic!("EOF reached"),
          }
        }
        let start = self.position;
        loop {
          match self.buffer.get(self.position) {
            Some(&b' ') | Some(&b'\n') | None => break,
            Some(_) => self.position += 1,
          }
        }
        &self.buffer[start..self.position]
      }

      fn read_line(&mut self) {
        self.position = 0;
        self.buffer.clear();
        self.reader.read_until(b'\n', &mut self.buffer).unwrap();
      }
    }
  }
}

Submission Info

Submission Time
Task B - Union Find
User kuretchi
Language Rust (1.15.1)
Score 100
Code Size 11476 Byte
Status AC
Exec Time 40 ms
Memory 6908 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 100 / 100
Status
AC × 1
AC × 19
Set Name Test Cases
Sample 00_sample_01.txt
All 00_sample_01.txt, subtask_01_01.txt, subtask_01_02.txt, subtask_01_03.txt, subtask_01_04.txt, subtask_01_05.txt, subtask_01_06.txt, subtask_01_07.txt, subtask_01_08.txt, subtask_01_09.txt, subtask_01_10.txt, subtask_01_11.txt, subtask_01_12.txt, subtask_01_13.txt, subtask_01_14.txt, subtask_01_15.txt, subtask_01_16.txt, subtask_01_17.txt, subtask_01_18.txt
Case Name Status Exec Time Memory
00_sample_01.txt AC 2 ms 4352 KB
subtask_01_01.txt AC 22 ms 4604 KB
subtask_01_02.txt AC 2 ms 6396 KB
subtask_01_03.txt AC 30 ms 5116 KB
subtask_01_04.txt AC 39 ms 6908 KB
subtask_01_05.txt AC 4 ms 4352 KB
subtask_01_06.txt AC 5 ms 6396 KB
subtask_01_07.txt AC 34 ms 4860 KB
subtask_01_08.txt AC 39 ms 6908 KB
subtask_01_09.txt AC 2 ms 4352 KB
subtask_01_10.txt AC 2 ms 6396 KB
subtask_01_11.txt AC 30 ms 4988 KB
subtask_01_12.txt AC 39 ms 6908 KB
subtask_01_13.txt AC 29 ms 4732 KB
subtask_01_14.txt AC 2 ms 6396 KB
subtask_01_15.txt AC 32 ms 4860 KB
subtask_01_16.txt AC 40 ms 6908 KB
subtask_01_17.txt AC 36 ms 6652 KB
subtask_01_18.txt AC 36 ms 6652 KB