結果
問題 |
No.3087 University Coloring
|
ユーザー |
|
提出日時 | 2025-04-04 22:28:31 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 58 ms / 2,000 ms |
コード長 | 2,332 bytes |
コンパイル時間 | 20,063 ms |
コンパイル使用メモリ | 403,892 KB |
実行使用メモリ | 16,724 KB |
最終ジャッジ日時 | 2025-04-12 02:36:28 |
合計ジャッジ時間 | 21,010 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 33 |
ソースコード
//#![allow(unused)] #[allow(unused_imports)] use std::{ cell::RefCell, convert::{Infallible, TryFrom, TryInto as _}, fmt::{self, Debug, Display, Formatter,}, fs::{File}, hash::{Hash, Hasher}, iter::{Product, Sum}, marker::PhantomData, ops::{Add, AddAssign, Sub, SubAssign, Div, DivAssign, Mul, MulAssign, Neg, RangeBounds}, str::{FromStr, SplitWhitespace}, sync::{atomic::{self, AtomicU32, AtomicU64}, Once}, collections::{*, btree_map::Range}, mem::{swap}, cmp::{self, Reverse, Ordering, Eq, PartialEq, PartialOrd}, thread::LocalKey, f64::consts::PI, time::Instant, rc::Rc, io::{self, stdin, Read, read_to_string, BufWriter, BufReader, stdout, Write}, }; #[allow(unused_imports)] use proconio::{input, input_interactive, marker::{*}}; #[allow(unused_imports)] //use rand::{thread_rng, Rng, seq::SliceRandom}; #[allow(unused_imports)] //use ac_library::{*}; #[allow(dead_code)] const INF: i64 = 1<<60; #[allow(dead_code)] const MOD: i64 = 1000000007; #[allow(dead_code)] const D: [(usize, usize); 4] = [(1, 0), (0, 1), (!0, 0), (0, !0)]; pub struct UnionFind{ parent: Vec<i32>, } impl UnionFind{ pub fn new(n: usize)->Self{ UnionFind{ parent: vec![-1; n], } } pub fn find(&mut self, r: usize)->usize{ if self.parent[r] < 0{return r;} let p = self.find(self.parent[r] as usize); self.parent[r] = p as i32; p } pub fn union(&mut self, u: usize, v: usize){ let (mut pu, mut pv) = (self.find(u), self.find(v)); if pu==pv{return;} if self.parent[pu] > self.parent[pv]{ swap(&mut pu, &mut pv); } self.parent[pu] += self.parent[pv]; self.parent[pv] = pu as i32; } pub fn same(&mut self, u: usize, v: usize)->bool{ self.find(u)==self.find(v) } pub fn size(&mut self, p: usize)->usize{ let r = self.find(p); (-self.parent[r]) as usize } } //use proconio::fastout; //#[fastout] fn main() { input! { n: usize, m: usize, mut e: [(Usize1,Usize1,i64); m], } let mut uf = UnionFind::new(n); let mut ans = 0; e.sort_by(|u, v| v.2.cmp(&u.2)); for &(u, v, w) in &e{ if uf.same(u, v){continue} uf.union(u, v); ans += 2*w; } println!("{}", ans); }