結果
問題 | No.1293 2種類の道路 |
ユーザー |
![]() |
提出日時 | 2020-11-20 23:42:44 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 44 ms / 2,000 ms |
コード長 | 3,267 bytes |
コンパイル時間 | 13,286 ms |
コンパイル使用メモリ | 384,520 KB |
実行使用メモリ | 6,948 KB |
最終ジャッジ日時 | 2024-07-23 13:59:38 |
合計ジャッジ時間 | 14,852 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 22 |
ソースコード
use std::io::{BufRead, BufWriter, Write, StdinLock, StdoutLock};fn input(stdin: &mut StdinLock) -> String {let mut input = String::new();stdin.read_line(&mut input).ok();input}macro_rules! read {($stdin:expr, [$t:tt; $n:expr]) => {(0..$n).map(|_| read!($stdin, $t)).collect::<Vec<_>>()};($stdin:expr, [$t:tt]) => {input($stdin).split_whitespace().map(|x| parse!(x, $t)).collect::<Vec<_>>()};($stdin:expr, ($($t:tt),*)) => {{let input = input($stdin);let mut iter = input.split_whitespace();( $( parse!(iter.next().unwrap(), $t) ),* )}};($stdin:expr, $t:tt) => {parse!(input($stdin).trim(), $t)};}macro_rules! parse {($s:expr, chars) => {$s.chars().collect::<Vec<_>>()};($s:expr, usize1) => {parse!($s, usize) - 1};($s:expr, $t:ty) => {$s.parse::<$t>().unwrap()}}trait ProconWrite {fn writeln<T: std::fmt::Display>(&mut self, x: T);fn writeln_iter<I: Iterator>(&mut self, iter: I)whereI::Item: std::fmt::Display{self.writeln(iter.map(|x| x.to_string()).collect::<Vec<_>>().join(" "));}}impl ProconWrite for BufWriter<StdoutLock<'_>> {fn writeln<T: std::fmt::Display>(&mut self, x: T) {writeln!(self, "{}", x).ok();}}struct Dsu {n: usize,parent_or_size: Vec<usize>,}impl Dsu {fn new(n: usize) -> Dsu {Dsu { n, parent_or_size: vec![!1; n] }}fn merge(&mut self, a: usize, b: usize) -> usize {let (mut x, mut y) = (self.leader(a), self.leader(b));if x == y { return x; }if !self.parent_or_size[x] < !self.parent_or_size[y] {std::mem::swap(&mut x, &mut y);}self.parent_or_size[x] -= !self.parent_or_size[y];self.parent_or_size[y] = x;x}fn leader(&mut self, a: usize) -> usize {if self.parent_or_size[a] >= self.n { return a; }self.parent_or_size[a] = self.leader(self.parent_or_size[a]);self.parent_or_size[a]}fn size(&mut self, a: usize) -> usize {let x = self.leader(a);!self.parent_or_size[x]}}fn solve(stdin: &mut StdinLock, writer: &mut BufWriter<StdoutLock>) {let (n, d, w) = read!(stdin, (usize, usize, usize));let mut car_dsu = Dsu::new(n);for _ in 0..d {let (a, b) = read!(stdin, (usize1, usize1));car_dsu.merge(a, b);}let mut walker_dsu = Dsu::new(n);for _ in 0..w {let (c, d) = read!(stdin, (usize1, usize1));walker_dsu.merge(c, d);}let mut ans = 0;let mut set = std::collections::HashSet::new();for i in 0..n {let x = car_dsu.leader(i);let y = walker_dsu.leader(i);if !set.insert((x, y)) { continue; }ans += car_dsu.size(x) * walker_dsu.size(y);}ans -= n;writer.writeln(ans);}fn main() {let stdin = std::io::stdin();let mut stdin = stdin.lock();let stdout = std::io::stdout();let mut writer = BufWriter::new(stdout.lock());solve(&mut stdin, &mut writer);}