#687063 (Rust) No.1639 最小通信路

• 問題: No.1639 最小通信路
• ユーザー: magurofly
• 提出日時: 2021-08-07 00:22:45
• 言語: Rust (1.77.0)
• 結果: AC
• 実行時間: 4 ms / 2,000 ms
• コード長: 16,519 bytes
• コンパイル時間: 7,029 ms
• コンパイル使用メモリ: 175,644 KB
• 実行使用メモリ: 4,348 KB
• 最終ジャッジ日時: 2023-10-17 05:58:24
• 合計ジャッジ時間: 3,936 ms
• ジャッジサーバーID （参考情報）: judge13 / judge11

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	1 ms; 4,348 KB
testcase_01	AC	1 ms; 4,348 KB
testcase_02	AC	2 ms; 4,348 KB
testcase_03	AC	4 ms; 4,348 KB
testcase_04	AC	4 ms; 4,348 KB
testcase_05	AC	1 ms; 4,348 KB
testcase_06	AC	1 ms; 4,348 KB
testcase_07	AC	1 ms; 4,348 KB
testcase_08	AC	2 ms; 4,348 KB
testcase_09	AC	1 ms; 4,348 KB
testcase_10	AC	1 ms; 4,348 KB
testcase_11	AC	1 ms; 4,348 KB
testcase_12	AC	1 ms; 4,348 KB
testcase_13	AC	2 ms; 4,348 KB
testcase_14	AC	1 ms; 4,348 KB
testcase_15	AC	1 ms; 4,348 KB
testcase_16	AC	1 ms; 4,348 KB
testcase_17	AC	2 ms; 4,348 KB
testcase_18	AC	1 ms; 4,348 KB
testcase_19	AC	1 ms; 4,348 KB
testcase_20	AC	1 ms; 4,348 KB
testcase_21	AC	1 ms; 4,348 KB
testcase_22	AC	1 ms; 4,348 KB
testcase_23	AC	1 ms; 4,348 KB
testcase_24	AC	1 ms; 4,348 KB
testcase_25	AC	1 ms; 4,348 KB
testcase_26	AC	1 ms; 4,348 KB
testcase_27	AC	1 ms; 4,348 KB
testcase_28	AC	1 ms; 4,348 KB
testcase_29	AC	2 ms; 4,348 KB
testcase_30	AC	2 ms; 4,348 KB
testcase_31	AC	1 ms; 4,348 KB
testcase_32	AC	2 ms; 4,348 KB
testcase_33	AC	1 ms; 4,348 KB
testcase_34	AC	2 ms; 4,348 KB
testcase_35	AC	3 ms; 4,348 KB
testcase_36	AC	2 ms; 4,348 KB
testcase_37	AC	2 ms; 4,348 KB
testcase_38	AC	1 ms; 4,348 KB
testcase_39	AC	1 ms; 4,348 KB
testcase_40	AC	1 ms; 4,348 KB
testcase_41	AC	2 ms; 4,348 KB
testcase_42	AC	3 ms; 4,348 KB
testcase_43	AC	1 ms; 4,348 KB
testcase_44	AC	1 ms; 4,348 KB

ソースコード

#![allow(dead_code, unused_imports, unused_macros, non_snake_case)]
/*#[fastout]
fn main() {
  input! {
    N: usize,
    edges: [(Usize1, Usize1, String); N * (N - 1) / 2],
  }

  let mut uf = UnionFind::new(N);
  let mut max_cost = "0".to_string();
  for (a, b, C) in edges {
    if uf.same(a, b) {
      continue;
    }
    uf.merge(a, b);
    max_cost = C;
  }

  println!("{}", max_cost);
}*/ pub use __cargo_equip::prelude::*;

fn main(){let __proconio_stdout=::std::io::stdout();let mut __proconio_stdout=::std::io::BufWriter::new(__proconio_stdout.lock());let __proconio_res={input!{N:usize,edges:[(Usize1,Usize1,String);N*(N-1)/2],}let mut uf=UnionFind::new(N);let mut max_cost="0".to_string();for(a,b,C)in edges{if uf.same(a,b){continue;}uf.merge(a,b);max_cost=C;}<::std::io::BufWriter<::std::io::StdoutLock>as::std::io::Write>::write_fmt(&mut __proconio_stdout,format_args!(concat!("{}","\n"),max_cost)).unwrap();};<::std::io::BufWriter<::std::io::StdoutLock>as::std::io::Write>::flush(&mut __proconio_stdout).unwrap();return __proconio_res;} 

type Int = i64;
const MOD: Int = 1_000_000_007;
const INF: Int = 1_000_000_000_000_000_000;
const YESNO: [&'static str; 2] = ["No", "Yes"];

use proconio::{input, /*fastout,*/ marker::{Chars, Bytes, Usize1}};
#[allow(unused_imports)]
use proconio::fastout;
use std::collections::*;
use std::cmp::{self, Reverse};

fn yesno(c: bool) { println!("{}", YESNO[c as usize]); }
fn yes() { yesno(true); }
fn no() { yesno(false); }

pub struct UnionFind(Vec<isize>, usize);
impl UnionFind {
  pub fn new(n: usize) -> Self { Self(vec![-1; n], n) }
  pub fn leader(&mut self, mut i: usize) -> usize { let k = self.0[i]; if k >= 0 { let j = self.leader(k as usize); self.0[i] = j as isize; i = j; }; i }
  pub fn merge(&mut self, mut i: usize, mut j: usize) -> bool { i = self.leader(i); j = self.leader(j); i != j && { if self.0[i] > self.0[j] { let k = i; i = j; j = k; }; self.0[i] += self.0[j]; self.0[j] = i as isize; true } }
  pub fn same(&mut self, i: usize, j: usize) -> bool { self.leader(i) == self.leader(j) }
  pub fn size(&mut self, mut i: usize) -> usize { i = self.leader(i); -self.0[i] as usize }
  pub fn groups(&mut self) -> Vec<Vec<usize>> { let mut s = vec![vec![]; self.1]; for i in 0 .. self.1 { s[self.leader(i)].push(i) }; s.into_iter().filter(|g| g.len() > 0 ).collect::<Vec<_>>() }
}

// The following code was expanded by `cargo-equip`.

#[rustfmt::skip]
#[allow(unused)]
mod __cargo_equip {
    pub(crate) mod crates {
        pub mod lazy_static {#![no_std]use crate::__cargo_equip::preludes::lazy_static::*;pub use crate::__cargo_equip::macros::lazy_static::*;#[path="inline_lazy.rs"]pub mod lazy{use crate::__cargo_equip::preludes::lazy_static::*;extern crate core;extern crate std;use self::std::prelude::v1::*;use self::std::cell::Cell;use self::std::hint::unreachable_unchecked;use self::std::sync::Once;#[allow(deprecated)]pub use self::std::sync::ONCE_INIT;pub struct Lazy<T:Sync>(Cell<Option<T> >,Once);impl<T:Sync>Lazy<T>{#[allow(deprecated)]pub const INIT:Self=Lazy(Cell::new(None),ONCE_INIT);#[inline(always)]pub fn get<F>(&'static self,f:F)->&T where F:FnOnce()->T,{self.1.call_once(| |{self.0.set(Some(f()));});unsafe{match*self.0.as_ptr(){Some(ref x)=>x,None=>{debug_assert!(false,"attempted to derefence an uninitialized lazy static. This is a bug");unreachable_unchecked()},}}}}unsafe impl<T:Sync>Sync for Lazy<T>{}}pub use core::ops::Deref as __Deref;pub trait LazyStatic{fn initialize(lazy:&Self);}pub fn initialize<T:LazyStatic>(lazy:&T){LazyStatic::initialize(lazy);}}
        pub mod proconio {#![allow(clippy::needless_doctest_main,clippy::print_literal)]use crate::__cargo_equip::preludes::proconio::*;pub use crate::__cargo_equip::macros::proconio::*;pub use proconio_derive::*;pub mod marker{use crate::__cargo_equip::preludes::proconio::*;pub enum Chars{}pub enum Bytes{}pub enum Usize1{}pub enum Isize1{}}pub mod read{use crate::__cargo_equip::preludes::proconio::*;use crate::__cargo_equip::crates::proconio::marker::{Bytes,Chars,Isize1,Usize1};use crate::__cargo_equip::crates::proconio::source::{Readable,Source};use std::any::type_name;use std::fmt::Debug;use std::io::BufRead;use std::str::FromStr;impl<T:FromStr>Readable for T where T::Err:Debug,{type Output=T;fn read<R:BufRead,S:Source<R> >(source:&mut S)->T{let token=source.next_token_unwrap();match token.parse(){Ok(v)=>v,Err(e)=>panic!(concat!("failed to parse the input `{input}` ","to the value of type `{ty}`: {err:?}; ","ensure that the input format is collectly specified ","and that the input value must handle specified type.",),input=token,ty=type_name::<T>(),err=e,),}}}impl Readable for Chars{type Output=Vec<char>;fn read<R:BufRead,S:Source<R> >(source:&mut S)->Vec<char>{source.next_token_unwrap().chars().collect()}}impl Readable for Bytes{type Output=Vec<u8>;fn read<R:BufRead,S:Source<R> >(source:&mut S)->Vec<u8>{source.next_token_unwrap().bytes().collect()}}impl Readable for Usize1{type Output=usize;fn read<R:BufRead,S:Source<R> >(source:&mut S)->usize{usize::read(source)-1}}impl Readable for Isize1{type Output=isize;fn read<R:BufRead,S:Source<R> >(source:&mut S)->isize{isize::read(source)-1}}}pub mod source{use crate::__cargo_equip::preludes::proconio::*;use std::io::BufRead;pub mod line{use crate::__cargo_equip::preludes::proconio::*;use super::Source;use std::io::BufRead;use std::iter::Peekable;use std::str::SplitWhitespace;pub struct LineSource<R:BufRead>{tokens:Peekable<SplitWhitespace<'static> >,current_context:Box<str>,reader:R,}impl<R:BufRead>LineSource<R>{pub fn new(reader:R)->LineSource<R>{LineSource{current_context:"".to_string().into_boxed_str(),tokens:"".split_whitespace().peekable(),reader,}}fn prepare(&mut self){while self.tokens.peek().is_none(){let mut line=String::new();let num_bytes=self.reader.read_line(&mut line).expect("failed to get linel maybe an IO error.");if num_bytes==0{return;}self.current_context=line.into_boxed_str();self.tokens=unsafe{std::mem::transmute::<_,&'static str>(&*self.current_context)}.split_whitespace().peekable();}}}impl<R:BufRead>Source<R>for LineSource<R>{fn next_token(&mut self)->Option<&str>{self.prepare();self.tokens.next()}fn is_empty(&mut self)->bool{self.prepare();self.tokens.peek().is_none()}}use std::io::BufReader;impl<'a>From<&'a str>for LineSource<BufReader<&'a[u8]> >{fn from(s:&'a str)->LineSource<BufReader<&'a[u8]> >{LineSource::new(BufReader::new(s.as_bytes()))}}}pub mod once{use crate::__cargo_equip::preludes::proconio::*;use super::Source;use std::io::BufRead;use std::iter::Peekable;use std::marker::PhantomData;use std::str::SplitWhitespace;pub struct OnceSource<R:BufRead>{tokens:Peekable<SplitWhitespace<'static> >,context:Box<str>,_read:PhantomData<R>,}impl<R:BufRead>OnceSource<R>{pub fn new(mut source:R)->OnceSource<R>{let mut context=String::new();source.read_to_string(&mut context).expect("failed to read from source; maybe an IO error.");let context=context.into_boxed_str();let mut res=OnceSource{context,tokens:"".split_whitespace().peekable(),_read:PhantomData,};use std::mem;let context:&'static str=unsafe{mem::transmute(&*res.context)};res.tokens=context.split_whitespace().peekable();res}}impl<R:BufRead>Source<R>for OnceSource<R>{fn next_token(&mut self)->Option<&str>{self.tokens.next()}fn is_empty(&mut self)->bool{self.tokens.peek().is_none()}}use std::io::BufReader;impl<'a>From<&'a str>for OnceSource<BufReader<&'a[u8]> >{fn from(s:&'a str)->OnceSource<BufReader<&'a[u8]> >{OnceSource::new(BufReader::new(s.as_bytes()))}}}pub mod auto{use crate::__cargo_equip::preludes::proconio::*;#[cfg(debug_assertions)]pub use super::line::LineSource as AutoSource;#[cfg(not(debug_assertions))]pub use super::once::OnceSource as AutoSource;}pub trait Source<R:BufRead>{fn next_token(&mut self)->Option<&str>;fn is_empty(&mut self)->bool;fn next_token_unwrap(&mut self)->&str{self.next_token().expect(concat!("failed to get the next token; ","maybe reader reached an end of input. ","ensure that arguments for `input!` macro is correctly ","specified to match the problem input."))}}impl<R:BufRead,S:Source<R> >Source<R>for&'_ mut S{fn next_token(&mut self)->Option<&str>{(*self).next_token()}fn is_empty(&mut self)->bool{(*self).is_empty()}}pub trait Readable{type Output;fn read<R:BufRead,S:Source<R> >(source:&mut S)->Self::Output;}}use crate::__cargo_equip::crates::proconio::source::auto::AutoSource;use lazy_static::lazy_static;use std::io;use std::io::{BufReader,Stdin};use std::sync::Mutex;lazy_static!{#[doc(hidden)]pub static ref STDIN_SOURCE:Mutex<AutoSource<BufReader<Stdin>>>=Mutex::new(AutoSource::new(BufReader::new(io::stdin())));}pub fn is_stdin_empty()->bool{use crate::__cargo_equip::crates::proconio::source::Source;let mut lock=STDIN_SOURCE.lock().expect(concat!("failed to lock the stdin; please re-run this program.  ","If this issue repeatedly occur, this is a bug in `proconio`.  ","Please report this issue from ","<https://github.com/statiolake/proconio-rs/issues>."));lock.is_empty()}}
        pub mod __proconio_derive_0_1_6 {pub use crate::__cargo_equip::macros::__proconio_derive_0_1_6::*;}
    }

    pub(crate) mod macros {
        pub mod lazy_static {pub use crate::{__macro_def_lazy_static___lazy_static_create as __lazy_static_create,__macro_def_lazy_static___lazy_static_internal as __lazy_static_internal,__macro_def_lazy_static_lazy_static as lazy_static};}
        pub mod proconio {pub use crate::{__macro_def_proconio_input as input,__macro_def_proconio_read_value as read_value};}
        pub mod __proconio_derive_0_1_6 {pub use crate::{__macro_def___proconio_derive_0_1_6_derive_readable as derive_readable,__macro_def___proconio_derive_0_1_6_fastout as fastout};}
    }

    pub(crate) mod prelude {pub use crate::__cargo_equip::{crates::*,macros::lazy_static::*};}

    mod preludes {
        pub mod lazy_static {pub(in crate::__cargo_equip)use crate::__cargo_equip::macros::lazy_static::*;}
        pub mod proconio {pub(in crate::__cargo_equip)use crate::__cargo_equip::macros::lazy_static::*;pub(in crate::__cargo_equip)use crate::__cargo_equip::crates::{lazy_static,__proconio_derive_0_1_6 as proconio_derive};}
        pub mod __proconio_derive_0_1_6 {}
    }
}

#[cfg_attr(any(), rustfmt::skip)]
const _: () = {
    #[macro_export] macro_rules! __macro_def___proconio_derive_0_1_6_derive_readable(($(_:tt)*)=>(::std::compile_error!("`derive_readable` from `proconio-derive 0.1.6` should have been expanded");));
    #[macro_export] macro_rules! __macro_def___proconio_derive_0_1_6_fastout(($(_:tt)*)=>(::std::compile_error!("`fastout` from `proconio-derive 0.1.6` should have been expanded");));
    #[macro_export] macro_rules! __macro_def_lazy_static___lazy_static_create(($NAME:ident,$T:ty)=>{static$NAME:$crate::__cargo_equip::crates::lazy_static::lazy::Lazy<$T> =$crate::__cargo_equip::crates::lazy_static::lazy::Lazy::INIT;});
    #[macro_export] macro_rules! __macro_def_lazy_static___lazy_static_internal(($(#[$attr:meta])*($($vis:tt)*)static ref$N:ident:$T:ty=$e:expr;$($t:tt)*)=>{__lazy_static_internal!(@MAKE TY,$(#[$attr])*,($($vis)*),$N);__lazy_static_internal!(@TAIL,$N:$T=$e);lazy_static!($($t)*);};(@TAIL,$N:ident:$T:ty=$e:expr)=>{impl$crate::__cargo_equip::crates::lazy_static::__Deref for$N{type Target=$T;fn deref(&self)->&$T{#[inline(always)]fn __static_ref_initialize()->$T{$e}#[inline(always)]fn __stability()->&'static$T{__lazy_static_create!(LAZY,$T);LAZY.get(__static_ref_initialize)}__stability()}}impl$crate::__cargo_equip::crates::lazy_static::LazyStatic for$N{fn initialize(lazy:&Self){let _=&**lazy;}}};(@MAKE TY,$(#[$attr:meta])*,($($vis:tt)*),$N:ident)=>{#[allow(missing_copy_implementations)]#[allow(non_camel_case_types)]#[allow(dead_code)]$(#[$attr])*$($vis)*struct$N{__private_field:()}#[doc(hidden)]$($vis)*static$N:$N=$N{__private_field:()};};()=>());
    #[macro_export] macro_rules! __macro_def_lazy_static_lazy_static(($(#[$attr:meta])*static ref$N:ident:$T:ty=$e:expr;$($t:tt)*)=>{__lazy_static_internal!($(#[$attr])*()static ref$N:$T=$e;$($t)*);};($(#[$attr:meta])*pub static ref$N:ident:$T:ty=$e:expr;$($t:tt)*)=>{__lazy_static_internal!($(#[$attr])*(pub)static ref$N:$T=$e;$($t)*);};($(#[$attr:meta])*pub($($vis:tt)+)static ref$N:ident:$T:ty=$e:expr;$($t:tt)*)=>{__lazy_static_internal!($(#[$attr])*(pub($($vis)+))static ref$N:$T=$e;$($t)*);};()=>());
    #[macro_export] macro_rules! __macro_def_proconio_input((@from[$source:expr]@rest)=>{};(@from[$source:expr]@rest mut$($rest:tt)*)=>{$crate::__cargo_equip::crates::proconio::input!{@from[$source]@mut[mut]@rest$($rest)*}};(@from[$source:expr]@rest$($rest:tt)*)=>{$crate::__cargo_equip::crates::proconio::input!{@from[$source]@mut[]@rest$($rest)*}};(@from[$source:expr]@mut[$($mut:tt)?]@rest$var:tt:$($rest:tt)*)=>{$crate::__cargo_equip::crates::proconio::input!{@from[$source]@mut[$($mut)*]@var$var@kind[]@rest$($rest)*}};(@from[$source:expr]@mut[$($mut:tt)?]@var$var:tt@kind[$($kind:tt)*]@rest)=>{let$($mut)*$var=$crate::__cargo_equip::crates::proconio::read_value!(@source[$source]@kind[$($kind)*]);};(@from[$source:expr]@mut[$($mut:tt)?]@var$var:tt@kind[$($kind:tt)*]@rest,$($rest:tt)*)=>{$crate::__cargo_equip::crates::proconio::input!(@from[$source]@mut[$($mut)*]@var$var@kind[$($kind)*]@rest);$crate::__cargo_equip::crates::proconio::input!(@from[$source]@rest$($rest)*);};(@from[$source:expr]@mut[$($mut:tt)?]@var$var:tt@kind[$($kind:tt)*]@rest$tt:tt$($rest:tt)*)=>{$crate::__cargo_equip::crates::proconio::input!(@from[$source]@mut[$($mut)*]@var$var@kind[$($kind)*$tt]@rest$($rest)*);};(from$source:expr,$($rest:tt)*)=>{#[allow(unused_variables,unused_mut)]let mut s=$source;$crate::__cargo_equip::crates::proconio::input!{@from[&mut s]@rest$($rest)*}};($($rest:tt)*)=>{let mut locked_stdin=$crate::__cargo_equip::crates::proconio::STDIN_SOURCE.lock().expect(concat!("failed to lock the stdin; please re-run this program.  ","If this issue repeatedly occur, this is a bug in `proconio`.  ","Please report this issue from ","<https://github.com/statiolake/proconio-rs/issues>."));$crate::__cargo_equip::crates::proconio::input!{@from[&mut*locked_stdin]@rest$($rest)*}drop(locked_stdin);};);
    #[macro_export] macro_rules! __macro_def_proconio_read_value((@source[$source:expr]@kind[[$($kind:tt)*]])=>{$crate::__cargo_equip::crates::proconio::read_value!(@array@source[$source]@kind[]@rest$($kind)*)};(@array@source[$source:expr]@kind[$($kind:tt)*]@rest)=>{{let len=<usize as$crate::__cargo_equip::crates::proconio::source::Readable>::read($source);$crate::__cargo_equip::crates::proconio::read_value!(@source[$source]@kind[[$($kind)*;len]])}};(@array@source[$source:expr]@kind[$($kind:tt)*]@rest;$($rest:tt)*)=>{$crate::__cargo_equip::crates::proconio::read_value!(@array@source[$source]@kind[$($kind)*]@len[$($rest)*])};(@array@source[$source:expr]@kind[$($kind:tt)*]@rest$tt:tt$($rest:tt)*)=>{$crate::__cargo_equip::crates::proconio::read_value!(@array@source[$source]@kind[$($kind)*$tt]@rest$($rest)*)};(@array@source[$source:expr]@kind[$($kind:tt)*]@len[$($len:tt)*])=>{{let len=$($len)*;(0..len).map(|_|$crate::__cargo_equip::crates::proconio::read_value!(@source[$source]@kind[$($kind)*])).collect::<Vec<_>>()}};(@source[$source:expr]@kind[($($kinds:tt)*)])=>{$crate::__cargo_equip::crates::proconio::read_value!(@tuple@source[$source]@kinds[]@current[]@rest$($kinds)*)};(@tuple@source[$source:expr]@kinds[$([$($kind:tt)*])*]@current[]@rest)=>{($($crate::__cargo_equip::crates::proconio::read_value!(@source[$source]@kind[$($kind)*]),)*)};(@tuple@source[$source:expr]@kinds[$($kinds:tt)*]@current[$($curr:tt)*]@rest)=>{$crate::__cargo_equip::crates::proconio::read_value!(@tuple@source[$source]@kinds[$($kinds)*[$($curr)*]]@current[]@rest)};(@tuple@source[$source:expr]@kinds[$($kinds:tt)*]@current[$($curr:tt)*]@rest,$($rest:tt)*)=>{$crate::__cargo_equip::crates::proconio::read_value!(@tuple@source[$source]@kinds[$($kinds)*[$($curr)*]]@current[]@rest$($rest)*)};(@tuple@source[$source:expr]@kinds[$($kinds:tt)*]@current[$($curr:tt)*]@rest$tt:tt$($rest:tt)*)=>{$crate::__cargo_equip::crates::proconio::read_value!(@tuple@source[$source]@kinds[$($kinds)*]@current[$($curr)*$tt]@rest$($rest)*)};(@source[$source:expr]@kind[])=>{compile_error!(concat!("Reached unreachable statement while parsing macro input.  ","This is a bug in `proconio`.  ","Please report this issue from ","<https://github.com/statiolake/proconio-rs/issues>."));};(@source[$source:expr]@kind[$kind:ty])=>{<$kind as$crate::__cargo_equip::crates::proconio::source::Readable>::read($source)});
};