結果
問題 | No.1293 2種類の道路 |
ユーザー |
![]() |
提出日時 | 2020-11-20 22:12:59 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 40 ms / 2,000 ms |
コード長 | 10,021 bytes |
コンパイル時間 | 14,288 ms |
コンパイル使用メモリ | 382,656 KB |
実行使用メモリ | 11,392 KB |
最終ジャッジ日時 | 2024-07-23 13:10:01 |
合計ジャッジ時間 | 15,995 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 22 |
ソースコード
// The main code is at the very bottom.#[allow(unused_imports)]use {lib::byte::ByteChar,std::cell::{Cell, RefCell},std::cmp::{self,Ordering::{self, *},Reverse,},std::collections::*,std::convert::identity,std::fmt::{self, Debug, Display, Formatter},std::io::prelude::*,std::iter::{self, FromIterator},std::marker::PhantomData,std::mem,std::num::Wrapping,std::ops::{Range, RangeFrom, RangeInclusive, RangeTo, RangeToInclusive},std::process,std::rc::Rc,std::thread,std::time::{Duration, Instant},std::{char, f32, f64, i128, i16, i32, i64, i8, isize, str, u128, u16, u32, u64, u8, usize},};#[allow(unused_imports)]#[macro_use]pub mod lib {pub mod byte {pub use self::byte_char::*;mod byte_char {use std::error::Error;use std::fmt::{self, Debug, Display, Formatter};use std::str::FromStr;#[derive(Clone, Copy, Default, PartialEq, Eq, PartialOrd, Ord, Hash)]#[repr(transparent)]pub struct ByteChar(pub u8);impl Debug for ByteChar {fn fmt(&self, f: &mut Formatter) -> fmt::Result {write!(f, "b'{}'", self.0 as char)}}impl Display for ByteChar {fn fmt(&self, f: &mut Formatter) -> fmt::Result {write!(f, "{}", self.0 as char)}}impl FromStr for ByteChar {type Err = ParseByteCharError;fn from_str(s: &str) -> Result<ByteChar, ParseByteCharError> {match s.as_bytes().len() {1 => Ok(ByteChar(s.as_bytes()[0])),0 => Err(ParseByteCharErrorKind::EmptyStr.into()),_ => Err(ParseByteCharErrorKind::TooManyBytes.into()),}}}#[derive(Clone, Copy, PartialEq, Eq, Hash, Debug)]pub struct ParseByteCharError {kind: ParseByteCharErrorKind,}impl Display for ParseByteCharError {fn fmt(&self, f: &mut Formatter) -> fmt::Result {f.write_str(match self.kind {ParseByteCharErrorKind::EmptyStr => "empty string",ParseByteCharErrorKind::TooManyBytes => "too many bytes",})}}impl Error for ParseByteCharError {}#[derive(Clone, Copy, PartialEq, Eq, Hash, Debug)]enum ParseByteCharErrorKind {EmptyStr,TooManyBytes,}impl From<ParseByteCharErrorKind> for ParseByteCharError {fn from(kind: ParseByteCharErrorKind) -> ParseByteCharError {ParseByteCharError { kind }}}}}pub mod io {pub use self::scanner::*;mod scanner {use std::io::{self, BufRead};use std::iter;use std::str::FromStr;#[derive(Debug)]pub struct Scanner<R> {reader: R,buf: String,pos: usize,}impl<R: BufRead> Scanner<R> {pub fn new(reader: R) -> Self {Scanner {reader,buf: String::new(),pos: 0,}}pub fn next(&mut self) -> io::Result<&str> {let start = loop {match self.rest().find(|c| c != ' ') {Some(i) => break i,None => self.fill_buf()?,}};self.pos += start;let len = self.rest().find(' ').unwrap_or(self.rest().len());let s = &self.buf[self.pos..][..len]; // self.rest()[..len]self.pos += len;Ok(s)}pub fn parse_next<T>(&mut self) -> io::Result<Result<T, T::Err>>whereT: FromStr,{Ok(self.next()?.parse())}pub fn parse_next_n<T>(&mut self, n: usize) -> io::Result<Result<Vec<T>, T::Err>>whereT: FromStr,{iter::repeat_with(|| self.parse_next()).take(n).collect()}pub fn map_next_bytes<T, F>(&mut self, mut f: F) -> io::Result<Vec<T>>whereF: FnMut(u8) -> T,{Ok(self.next()?.bytes().map(&mut f).collect())}pub fn map_next_bytes_n<T, F>(&mut self, n: usize, mut f: F) -> io::Result<Vec<Vec<T>>>whereF: FnMut(u8) -> T,{iter::repeat_with(|| self.map_next_bytes(&mut f)).take(n).collect()}fn rest(&self) -> &str {&self.buf[self.pos..]}fn fill_buf(&mut self) -> io::Result<()> {self.buf.clear();self.pos = 0;let read = self.reader.read_line(&mut self.buf)?;if read == 0 {return Err(io::ErrorKind::UnexpectedEof.into());}if *self.buf.as_bytes().last().unwrap() == b'\n' {self.buf.pop();}Ok(())}}}}}#[allow(dead_code)]mod ac_library_rs {pub mod dsu {pub struct Dsu {n: usize,parent_or_size: Vec<i32>,}impl Dsu {pub fn new(size: usize) -> Self {Self {n: size,parent_or_size: vec![-1; size],}}pub fn merge(&mut self, a: usize, b: usize) -> usize {assert!(a < self.n);assert!(b < self.n);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 as i32;x}pub fn same(&mut self, a: usize, b: usize) -> bool {assert!(a < self.n);assert!(b < self.n);self.leader(a) == self.leader(b)}pub fn leader(&mut self, a: usize) -> usize {assert!(a < self.n);if self.parent_or_size[a] < 0 {return a;}self.parent_or_size[a] = self.leader(self.parent_or_size[a] as usize) as i32;self.parent_or_size[a] as usize}pub fn size(&mut self, a: usize) -> usize {assert!(a < self.n);let x = self.leader(a);-self.parent_or_size[x] as usize}pub fn groups(&mut self) -> Vec<Vec<usize>> {let mut leader_buf = vec![0; self.n];let mut group_size = vec![0; self.n];for i in 0..self.n {leader_buf[i] = self.leader(i);group_size[leader_buf[i]] += 1;}let mut result = vec![Vec::new(); self.n];for i in 0..self.n {result[i].reserve(group_size[i]);}for i in 0..self.n {result[leader_buf[i]].push(i);}result.into_iter().filter(|x| !x.is_empty()).collect::<Vec<Vec<usize>>>()}}}pub use self::dsu::Dsu;}#[allow(unused_macros)]macro_rules! eprint {($($arg:tt)*) => {if cfg!(debug_assertions) {std::eprint!($($arg)*)}};}#[allow(unused_macros)]macro_rules! eprintln {($($arg:tt)*) => {if cfg!(debug_assertions) {std::eprintln!($($arg)*)}};}#[allow(unused_macros)]macro_rules! dbg {($($arg:tt)*) => {if cfg!(debug_assertions) {std::dbg!($($arg)*)} else {($($arg)*)}};}const CUSTOM_STACK_SIZE_MIB: Option<usize> = Some(1024);const INTERACTIVE: bool = false;fn main() -> std::io::Result<()> {match CUSTOM_STACK_SIZE_MIB {Some(stack_size_mib) => std::thread::Builder::new().name("run_solver".to_owned()).stack_size(stack_size_mib * 1024 * 1024).spawn(run_solver)?.join().unwrap(),None => run_solver(),}}fn run_solver() -> std::io::Result<()> {let stdin = std::io::stdin();let reader = stdin.lock();let stdout = std::io::stdout();let writer = stdout.lock();macro_rules! with_wrapper {($($wrapper:expr)?) => {{let mut writer = $($wrapper)?(writer);solve(reader, &mut writer)?;writer.flush()}};}if cfg!(debug_assertions) || INTERACTIVE {with_wrapper!()} else {with_wrapper!(std::io::BufWriter::new)}}fn solve<R, W>(reader: R, mut writer: W) -> std::io::Result<()>whereR: BufRead,W: Write,{let mut _scanner = lib::io::Scanner::new(reader);#[allow(unused_macros)]macro_rules! scan {($T:ty) => {_scanner.parse_next::<$T>()?.unwrap()};($($T:ty),+) => {($(scan!($T)),+)};($T:ty; $n:expr) => {_scanner.parse_next_n::<$T>($n)?.unwrap()};($($T:ty),+; $n:expr) => {iter::repeat_with(|| -> std::io::Result<_> { Ok(($(scan!($T)),+)) }).take($n).collect::<std::io::Result<Vec<_>>>()?};}#[allow(unused_macros)]macro_rules! scan_bytes_map {($f:expr) => {_scanner.map_next_bytes($f)?};($f:expr; $n:expr) => {_scanner.map_next_bytes_n($n, $f)?};}#[allow(unused_macros)]macro_rules! print {($($arg:tt)*) => {write!(writer, $($arg)*)?};}#[allow(unused_macros)]macro_rules! println {($($arg:tt)*) => {writeln!(writer, $($arg)*)?};}#[allow(unused_macros)]macro_rules! answer {($($arg:tt)*) => {{println!($($arg)*);return Ok(());}};}{use ac_library_rs::Dsu;let (n, d, w) = scan!(usize, usize, usize);let mut d_uf = Dsu::new(n);let mut w_uf = Dsu::new(n);for _ in 0..d {let (a, b) = scan!(usize, usize);d_uf.merge(a - 1, b - 1);}for _ in 0..w {let (c, d) = scan!(usize, usize);w_uf.merge(c - 1, d - 1);}let mut ans = 0u64;for v in d_uf.groups() {let i = v[0];ans += d_uf.size(i) as u64* v.iter().map(|&j| w_uf.leader(j)).collect::<HashSet<_>>().into_iter().map(|j| w_uf.size(j)).sum::<usize>() as u64;}ans -= n as u64;println!("{}", ans);}#[allow(unreachable_code)]Ok(())}