結果
問題 | No.1293 2種類の道路 |
ユーザー |
![]() |
提出日時 | 2020-11-20 23:53:33 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 69 ms / 2,000 ms |
コード長 | 2,975 bytes |
コンパイル時間 | 12,990 ms |
コンパイル使用メモリ | 382,968 KB |
実行使用メモリ | 17,464 KB |
最終ジャッジ日時 | 2024-07-23 14:03:03 |
合計ジャッジ時間 | 15,432 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 22 |
コンパイルメッセージ
warning: unused variable: `i` --> src/main.rs:23:9 | 23 | for i in 0..d { | ^ help: if this is intentional, prefix it with an underscore: `_i` | = note: `#[warn(unused_variables)]` on by default warning: unused variable: `i` --> src/main.rs:30:9 | 30 | for i in 0..w { | ^ help: if this is intentional, prefix it with an underscore: `_i` warning: method `same` is never used --> src/main.rs:92:8 | 73 | impl UnionFindTree { | ------------------ method in this implementation ... 92 | fn same(&mut self, x: usize, y: usize) -> bool { | ^^^^ | = note: `#[warn(dead_code)]` on by default
ソースコード
#![allow(unused_imports)]use std::cmp::*;use std::collections::*;use std::io::Write;use std::ops::Bound::*;#[allow(unused_macros)]macro_rules! debug {($($e:expr),*) => {#[cfg(debug_assertions)]$({let (e, mut err) = (stringify!($e), std::io::stderr());writeln!(err, "{} = {:?}", e, $e).unwrap()})*};}fn main() {let v = read_vec::<usize>();let (n, d, w) = (v[0], v[1], v[2]);let mut uft1 = UnionFindTree::new(n);for i in 0..d {let v = read_vec::<usize>();let (a, b) = (v[0] - 1, v[1] - 1);uft1.unite(a, b);}let mut uft2 = UnionFindTree::new(n);for i in 0..w {let v = read_vec::<usize>();let (a, b) = (v[0] - 1, v[1] - 1);uft2.unite(a, b);}let mut s = vec![HashSet::new(); n];let mut size = vec![0i64; n];for i in 0..n {let a = uft1.find(i);let b = uft2.find(i);if s[a].insert(b) {size[a] += uft2.get_size(b) as i64;}}let mut ans = 0;for i in 0..n {ans += uft1.get_size(i) as i64 * size[i];}println!("{}", ans - n as i64);}fn read<T: std::str::FromStr>() -> T {let mut s = String::new();std::io::stdin().read_line(&mut s).ok();s.trim().parse().ok().unwrap()}fn read_vec<T: std::str::FromStr>() -> Vec<T> {read::<String>().split_whitespace().map(|e| e.parse().ok().unwrap()).collect()}#[derive(Debug, Clone)]struct UnionFindTree {parent: Vec<isize>,size: Vec<usize>,height: Vec<u64>,}impl UnionFindTree {fn new(n: usize) -> UnionFindTree {UnionFindTree {parent: vec![-1; n],size: vec![1usize; n],height: vec![0u64; n],}}fn find(&mut self, index: usize) -> usize {if self.parent[index] == -1 {return index;}let idx = self.parent[index] as usize;let ret = self.find(idx);self.parent[index] = ret as isize;ret}fn same(&mut self, x: usize, y: usize) -> bool {self.find(x) == self.find(y)}fn get_size(&mut self, x: usize) -> usize {let idx = self.find(x);self.size[idx]}fn unite(&mut self, index0: usize, index1: usize) -> bool {let a = self.find(index0);let b = self.find(index1);if a == b {false} else {if self.height[a] > self.height[b] {self.parent[b] = a as isize;self.size[a] += self.size[b];} else if self.height[a] < self.height[b] {self.parent[a] = b as isize;self.size[b] += self.size[a];} else {self.parent[b] = a as isize;self.size[a] += self.size[b];self.height[a] += 1;}true}}}