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 |
|
|
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 |