結果

問題 No.1293 2種類の道路
ユーザー Strorkis
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

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)
where
I::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);
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0