結果
問題 | No.2403 "Eight" Bridges of Königsberg |
ユーザー | zeronosu77108 |
提出日時 | 2023-08-04 22:20:56 |
言語 | Rust (1.77.0 + proconio) |
結果 |
WA
|
実行時間 | - |
コード長 | 4,995 bytes |
コンパイル時間 | 14,878 ms |
コンパイル使用メモリ | 384,420 KB |
実行使用メモリ | 25,728 KB |
最終ジャッジ日時 | 2024-10-14 20:20:12 |
合計ジャッジ時間 | 16,191 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
5,248 KB |
testcase_01 | AC | 1 ms
5,248 KB |
testcase_02 | AC | 1 ms
5,248 KB |
testcase_03 | AC | 1 ms
5,248 KB |
testcase_04 | AC | 25 ms
12,560 KB |
testcase_05 | AC | 49 ms
22,264 KB |
testcase_06 | AC | 55 ms
23,148 KB |
testcase_07 | AC | 31 ms
15,484 KB |
testcase_08 | AC | 38 ms
17,312 KB |
testcase_09 | AC | 57 ms
25,136 KB |
testcase_10 | AC | 50 ms
25,184 KB |
testcase_11 | AC | 41 ms
18,964 KB |
testcase_12 | AC | 55 ms
25,728 KB |
testcase_13 | AC | 41 ms
17,372 KB |
testcase_14 | AC | 1 ms
5,248 KB |
testcase_15 | AC | 1 ms
5,248 KB |
testcase_16 | AC | 1 ms
5,248 KB |
testcase_17 | WA | - |
testcase_18 | WA | - |
testcase_19 | WA | - |
testcase_20 | WA | - |
testcase_21 | WA | - |
testcase_22 | WA | - |
testcase_23 | WA | - |
testcase_24 | WA | - |
testcase_25 | WA | - |
testcase_26 | WA | - |
testcase_27 | WA | - |
testcase_28 | WA | - |
testcase_29 | WA | - |
testcase_30 | WA | - |
testcase_31 | WA | - |
testcase_32 | WA | - |
testcase_33 | WA | - |
testcase_34 | WA | - |
ソースコード
use std::collections::BTreeSet; fn main() { let mut sc = Scanner::new(); let n = sc.usize(); let m = sc.usize(); let edges = sc.edges(m); let mut uni = UnionFind::new(n); let mut in_cnt = vec![0; n]; let mut out_cnt = vec![0; n]; for &(a, b) in &edges { out_cnt[a] += 1; in_cnt[b] += 1; uni.merge(a, b); } // for i in 0..n { eprintln!("{} : {} {}", i, in_cnt[i], out_cnt[i]); } let mut ng = BTreeSet::new(); for i in 0..n { if in_cnt[i] == out_cnt[i] { continue } ng.insert((in_cnt[i] - out_cnt[i], i)); } let mut ans = 0; while ng.len() > 2 { let (max, i) = *ng.iter().next_back().unwrap(); let (min, j) = *ng.iter().next().unwrap(); if signum(max) == signum(min) { break } let diff = max.min(-min); ng.remove(&(max, i)); ng.remove(&(min, j)); out_cnt[i] += diff; in_cnt[j] += diff; ans += diff; if max > diff { if max - diff != 0 { ng.insert((max - diff, i)); } } else { if min + diff != 0 { ng.insert((min + diff, j)); } } } let mut g = 0; for i in 0..n { if uni.size(i) == 1 { continue }; if uni.root(i) != i { continue } g += 1; } ans += g - 1; if ng.len() == 0 { println!("{}", ans); } else if ng.len() == 1 { let (c, _) = *ng.iter().next().unwrap(); println!("{}", ans + 1.max(c)); } else if ng.len() == 2 { let (max, _) = *ng.iter().next_back().unwrap(); let (min, _) = *ng.iter().next().unwrap(); if signum(max) == signum(min) { println!("{}", ans + max.abs() + min.abs()); } else { if max == -min { println!("{}", ans + max.abs() - 1); } else { let diff = max.min(-min); let m = max.max(-min); println!("{}", ans + diff + (m - diff)); } } } } fn signum(x: i64) -> i64 { if x == 0 { 0 } else if x > 0 { 1 } else { -1 } } struct Scanner { s : std::collections::VecDeque<String> } #[allow(unused)] impl Scanner { fn new() -> Self { use std::io::Read; let mut s = String::new(); std::io::stdin().read_to_string(&mut s).unwrap(); Self { s : s.split_whitespace().map(|s| s.to_string()).collect() } } fn reload(&mut self) -> () { use std::io::Read; let mut s = String::new(); std::io::stdin().read_to_string(&mut s).unwrap(); self.s = s.split_whitespace().map(|s| s.to_string()).collect(); } fn usize(&mut self) -> usize { self.input() } fn usize1(&mut self) -> usize { self.input::<usize>() - 1 } fn isize(&mut self) -> isize { self.input() } fn i32(&mut self) -> i32 { self.input() } fn i64(&mut self) -> i64 { self.input() } fn i128(&mut self) -> i128 { self.input() } fn u8(&mut self) -> u8 { self.input() } fn u32(&mut self) -> u32 { self.input() } fn u64(&mut self) -> u64 { self.input() } fn u128(&mut self) -> u128 { self.input() } fn edge(&mut self) -> (usize, usize) { (self.usize1(), self.usize1()) } fn edges(&mut self, m : usize) -> Vec<(usize, usize)> { let mut e = Vec::with_capacity(m); for _ in 0..m { e.push(self.edge()); } e } fn wedge<T:std::str::FromStr>(&mut self) -> (usize, usize, T) { (self.usize1(), self.usize1(), self.input()) } fn wedges<T:std::str::FromStr>(&mut self, m : usize) -> Vec<(usize, usize, T)> { let mut e = Vec::with_capacity(m); for _ in 0..m { e.push(self.wedge()); } e } fn input<T>(&mut self) -> T where T: std::str::FromStr { if self.s.is_empty() { self.reload(); } if let Some(head) = self.s.pop_front() { head.parse::<T>().ok().unwrap() } else { panic!() } } fn tuple<T, U>(&mut self) -> (T, U) where T: std::str::FromStr, U: std::str::FromStr { (self.input(), self.input()) } fn vec<T>(&mut self, n: usize) -> Vec<T> where T: std::str::FromStr { if self.s.is_empty() { self.reload(); } self.s.drain(..n).map(|s| s.parse::<T>().ok().unwrap() ).collect::<Vec<T>>() } fn nvec<T>(&mut self) -> Vec<T> where T: std::str::FromStr { let n : usize = self.input(); self.vec(n) } fn chars(&mut self) -> Vec<char> { let s : String = self.input(); s.chars().collect() } fn bytes(&mut self) -> Vec<u8> { let s : String = self.input(); s.bytes().collect() } } struct UnionFind { per : Vec<Option<usize>>, size : Vec<usize> } #[allow(dead_code)] impl UnionFind { fn new (n : usize) -> Self { Self { per : vec![None; n+1], size: vec![1; n+1]} } fn root (&mut self, x : usize) -> usize { if let Some(y) = self.per[x] { let res = self.root(y); self.per[x] = Some(res); res } else { x } } fn merge(&mut self, mut x : usize, mut y : usize) -> bool { x = self.root(x); y = self.root(y); if x == y { return false; } if self.size[x] < self.size[y] { std::mem::swap(&mut x, &mut y); } self.per[y] = Some(x); self.size[x] += self.size[y]; true } fn same(&mut self, x : usize, y : usize) -> bool { self.root(x) == self.root(y) } fn size(&mut self, x : usize) -> usize { let x = self.root(x); self.size[x] } }