結果
| 問題 | No.2337 Equidistant |
| ユーザー |
 tipstar0125
|
| 提出日時 | 2023-06-02 22:34:41 |
| 言語 | Rust (1.83.0 + proconio) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 6,699 bytes |
| コンパイル時間 | 15,943 ms |
| コンパイル使用メモリ | 383,864 KB |
| 実行使用メモリ | 11,448 KB |
| 最終ジャッジ日時 | 2024-12-28 20:11:24 |
| 合計ジャッジ時間 | 20,386 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 3 WA * 25 |
ソースコード
#![allow(non_snake_case)]#![allow(unused_imports)]#![allow(unused_macros)]#![allow(clippy::needless_range_loop)]#![allow(clippy::comparison_chain)]#![allow(clippy::nonminimal_bool)]#![allow(clippy::neg_multiply)]#![allow(dead_code)]use std::cmp::Reverse;use std::collections::{BTreeMap, BTreeSet, BinaryHeap, VecDeque};#[derive(Default)]struct Solver {}impl Solver {fn solve(&mut self) {input! {N: usize,Q: usize,AB: [(usize1, usize1); N - 1],ST: [(usize1, usize1); Q]}let mut wuf = WeightedUnionFind::new(N);for &(a, b) in &AB {wuf.unite(a, b, 1);}for &(s, t) in &ST {if wuf.diff(s, t) % 2 == 0 {println!("1");} else {println!("0");}}}}fn main() {std::thread::Builder::new().stack_size(128 * 1024 * 1024).spawn(|| Solver::default().solve()).unwrap().join().unwrap();}#[derive(Debug, Clone)]struct WeightedUnionFind {parent: Vec<isize>,size: usize,diff_weight: Vec<isize>,}impl WeightedUnionFind {fn new(n: usize) -> Self {WeightedUnionFind {parent: vec![-1; n],size: n,diff_weight: vec![0_isize; n],}}fn find(&mut self, x: usize) -> usize {if self.parent[x] < 0 {return x;}let root = self.find(self.parent[x] as usize);self.diff_weight[x] += self.diff_weight[self.parent[x] as usize];self.parent[x] = root as isize;root}fn weight(&mut self, x: usize) -> isize {self.find(x);self.diff_weight[x]}fn unite(&mut self, x: usize, y: usize, w: isize) -> Option<(usize, usize)> {let root_x = self.find(x);let root_y = self.find(y);if root_x == root_y {return None;}let adjusted_w = w + self.weight(x) - self.weight(y);let size_x = -self.parent[root_x];let size_y = -self.parent[root_y];self.size -= 1;if size_x >= size_y {self.diff_weight[root_y] = adjusted_w;self.parent[root_x] -= size_y;self.parent[root_y] = root_x as isize;Some((root_x, root_y))} else {self.diff_weight[root_x] = -adjusted_w;self.parent[root_y] -= size_x;self.parent[root_x] = root_y as isize;Some((root_y, root_x))}}fn is_same(&mut self, x: usize, y: usize) -> bool {self.find(x) == self.find(y)}fn is_root(&mut self, x: usize) -> bool {self.find(x) == x}fn diff(&mut self, x: usize, y: usize) -> isize {self.weight(y) - self.weight(x)}fn get_union_size(&mut self, x: usize) -> usize {let root = self.find(x);-self.parent[root] as usize}fn get_size(&self) -> usize {self.size}fn roots(&self) -> Vec<usize> {(0..self.parent.len()).filter(|i| self.parent[*i] < 0).collect::<Vec<usize>>()}fn members(&mut self, x: usize) -> Vec<usize> {let root = self.find(x);(0..self.parent.len()).filter(|i| self.find(*i) == root).collect::<Vec<usize>>()}fn all_group_members(&mut self) -> BTreeMap<usize, Vec<usize>> {let mut groups_map: BTreeMap<usize, Vec<usize>> = BTreeMap::new();for x in 0..self.parent.len() {let r = self.find(x);groups_map.entry(r).or_default().push(x);}groups_map}}#[macro_export]macro_rules! input {() => {};(mut $var:ident: $t:tt, $($rest:tt)*) => {let mut $var = __input_inner!($t);input!($($rest)*)};($var:ident: $t:tt, $($rest:tt)*) => {let $var = __input_inner!($t);input!($($rest)*)};(mut $var:ident: $t:tt) => {let mut $var = __input_inner!($t);};($var:ident: $t:tt) => {let $var = __input_inner!($t);};}#[macro_export]macro_rules! __input_inner {(($($t:tt),*)) => {($(__input_inner!($t)),*)};([$t:tt; $n:expr]) => {(0..$n).map(|_| __input_inner!($t)).collect::<Vec<_>>()};([$t:tt]) => {{let n = __input_inner!(usize);(0..n).map(|_| __input_inner!($t)).collect::<Vec<_>>()}};(chars) => {__input_inner!(String).chars().collect::<Vec<_>>()};(bytes) => {__input_inner!(String).into_bytes()};(usize1) => {__input_inner!(usize) - 1};($t:ty) => {$crate::read::<$t>()};}#[macro_export]macro_rules! println {() => {$crate::write(|w| {use std::io::Write;std::writeln!(w).unwrap()})};($($arg:tt)*) => {$crate::write(|w| {use std::io::Write;std::writeln!(w, $($arg)*).unwrap()})};}#[macro_export]macro_rules! print {($($arg:tt)*) => {$crate::write(|w| {use std::io::Write;std::write!(w, $($arg)*).unwrap()})};}#[macro_export]macro_rules! flush {() => {$crate::write(|w| {use std::io::Write;w.flush().unwrap()})};}pub fn read<T>() -> TwhereT: std::str::FromStr,T::Err: std::fmt::Debug,{use std::cell::RefCell;use std::io::*;thread_local! {pub static STDIN: RefCell<StdinLock<'static>> = RefCell::new(stdin().lock());}STDIN.with(|r| {let mut r = r.borrow_mut();let mut s = vec![];loop {let buf = r.fill_buf().unwrap();if buf.is_empty() {break;}if let Some(i) = buf.iter().position(u8::is_ascii_whitespace) {s.extend_from_slice(&buf[..i]);r.consume(i + 1);if !s.is_empty() {break;}} else {s.extend_from_slice(buf);let n = buf.len();r.consume(n);}}std::str::from_utf8(&s).unwrap().parse().unwrap()})}pub fn write<F>(f: F)whereF: FnOnce(&mut std::io::BufWriter<std::io::StdoutLock>),{use std::cell::RefCell;use std::io::*;thread_local! {pub static STDOUT: RefCell<BufWriter<StdoutLock<'static>>> =RefCell::new(BufWriter::new(stdout().lock()));}STDOUT.with(|w| f(&mut w.borrow_mut()))}