Rust の Vec の sort_by_key は気をつけて使おう
当たり前っちゃ当たり前だが、
vec.sort_by_key(|&value| heavy_function(value));
みたいなことをすると、 heavy_function が比較のたびに呼ばれるので、ソートが遅くなる。これは sort_by_cached_key でなんとかなるっぽい。
sort_by_key は
This sort is stable (i.e. does not reorder equal elements) and O(m n log(m n)) worst-case, where the key function is O(m).
sort_by_cached_key は
During sorting, the key function is called only once per element.
This sort is stable (i.e. does not reorder equal elements) and O(m n + n log n) worst-case, where the key function is O(m).
AtCoder Problems を色々いじった
この記事は AtCoder関連サービス Advent Calendar 2018 - Adventar の一部です。毎年なぜか12月になるとウェブアプリを触りたくなる。
kimiyuki さんが DB に index を張ってくれた
なぜか今まで index を張っていなかったのが無事張られた。これによって、あるユーザーについての提出一覧を取得するのが高速化された。
ユーザー情報 API を作った
今まではユーザー情報を表示するために、「AC 数ランキング」「Rated Point ランキング」「使用言語のランキング」を取得していた。これらはそれぞれ、「ユーザーの AC 数が上から何番目か」「ユーザーの Point が上から何番目か」「ユーザーがある言語で解いた問題数が、その言語の中で何番目か」を表示するのに使われていた。これらを表示するためにわざわざランキングを取得しているのは、もともとあったランキング API を流用してユーザーページを作ったという歴史的経緯によるものである。実際には意外にユーザーページを見る人が多く、不必要なランキング取得によって表示が遅いなどの問題があった。今回は、ユーザーについて必要な情報だけ返す API を新しく作り、表示を高速化された。
https://github.com/kenkoooo/AtCoderProblems/pull/73github.com
ユーザー共通のファイルは静的ファイルに書き出すようにした
ユーザーごとの提出一覧は DB に問い合わせる必要があるが、それ以外の API は静的な JSON ファイルに書き出すようにした。もともと、これらの API は叩かれても 304 を返すようにしていたが、そのへんは nginx でやってくださいという気持ちになった。あとは API サーバーが落ちてても表面的には動いていてほしいというのもある。
https://github.com/kenkoooo/AtCoderProblems/pull/82github.com
AGC 029 C - Lexicographic constraints
解法
できるだけ、辞書準最小のリストを作ることを目指す。例えばA=[2, 2]の時は["aa","bb"]でもよいが、["aa", "ab"] が辞書準最小のリストになる。
この時、一つ前の要素よりも大きい時は、一つ前の文字列の後ろに "a" を連続で追加すればよく、そうでない時は、その要素の末尾を1つインクリメントすれば良い。どういうことかと言うと、例えば A=[3, 3, 3, 5, 3, 3] のとき、2種類だけの文字列で作るとすると文字列のリストは["aaa", "aab", "aba", "abaaa", "abb", "baa"] のようになる。これは二進数で表した整数の適当な桁を1ずつ増加させていく単純な操作であることが分かる。
よってx種類の文字で構築可能かどうかは、x進数で操作した時に桁あふれのような状態にならないかどうかで判定できる。あとはこれを二分探索すれば良い。
コード
use std::collections::BTreeMap; fn solve(a: &Vec<usize>, color: usize) -> bool { let n = a.len(); let mut big = Big { map: BTreeMap::new(), color: color, }; let mut start = 0; for i in 1..n { if a[i] <= a[i - 1] { big.increment(a[i]); start = i + 1; break; } } for i in start..n { if a[i] <= a[i - 1] { big.resize(a[i]); if !big.increment(a[i]) { return false; } } } true } fn main() { let s = std::io::stdin(); let mut sc = Scanner { reader: s.lock() }; let n: usize = sc.read(); let a: Vec<usize> = sc.read_vec(n); if (1..n).all(|i| a[i] > a[i - 1]) { println!("1"); return; } let mut ng = 0; let mut ok = n; while ok - ng > 1 { let mid = (ok + ng) / 2; if solve(&a, mid) { ok = mid; } else { ng = mid; } } println!("{}", ok + 1); } struct Big { map: BTreeMap<usize, usize>, color: usize, } impl Big { fn increment(&mut self, index: usize) -> bool { if let Some(&v) = self.map.get(&index) { if v == self.color { self.map.remove(&index); if index == 1 { false } else { self.increment(index - 1) } } else { *self.map.get_mut(&index).unwrap() += 1; true } } else { self.map.insert(index, 1); true } } fn resize(&mut self, s: usize) { while let Some(&key) = self.map.keys().next_back() { if key > s { self.map.remove(&key); } else { break; } } } } pub struct Scanner<R> { reader: R, } impl<R: std::io::Read> Scanner<R> { pub fn read<T: std::str::FromStr>(&mut self) -> T { use std::io::Read; let buf = self .reader .by_ref() .bytes() .map(|b| b.unwrap()) .skip_while(|&b| b == b' ' || b == b'\n') .take_while(|&b| b != b' ' && b != b'\n') .collect::<Vec<_>>(); unsafe { std::str::from_utf8_unchecked(&buf) } .parse() .ok() .expect("Parse error.") } pub fn read_vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> { (0..n).map(|_| self.read()).collect() } pub fn chars(&mut self) -> Vec<char> { self.read::<String>().chars().collect() } }
AGC 029 D - Grid game
解法
まず先手が能動的にパスを選択することはありえない。なので、後手は先手の進行方向に障害物を置きさえすれば良い。
両プレーヤーが能動的にパスを選択せずにxターンが終了した時の位置を (x, y) とする。このとき、後手は適当にパスを挟むことでxターンが終了したときの位置を (x,1)〜(x,y) から選ぶことが出来る。つまり、xターン終了時に (x+1, 1) 〜 (x+1, y) のどこかに障害物があるならば x+1 ターン目で先手はパスせざるを得なくなる。
コード
use std::collections::{BTreeMap, BTreeSet}; fn main() { let s = std::io::stdin(); let mut sc = Scanner { reader: s.lock() }; let h: usize = sc.read(); let w: usize = sc.read(); let n: usize = sc.read(); let mut map = BTreeMap::new(); for _ in 0..n { let x: usize = sc.read(); let y: usize = sc.read(); map.entry(x).or_insert(BTreeSet::new()).insert(y); } let mut y = 1; for x in 1..(h + 1) { if let Some(set) = map.get(&(x + 1)) { if set.range(..(y + 1)).next().is_some() { println!("{}", x); return; } if !set.contains(&(y + 1)) { y += 1; } } else { y += 1; } } println!("{}", h); } pub struct Scanner<R> { reader: R, } impl<R: std::io::Read> Scanner<R> { pub fn read<T: std::str::FromStr>(&mut self) -> T { use std::io::Read; let buf = self .reader .by_ref() .bytes() .map(|b| b.unwrap()) .skip_while(|&b| b == b' ' || b == b'\n') .take_while(|&b| b != b' ' && b != b'\n') .collect::<Vec<_>>(); unsafe { std::str::from_utf8_unchecked(&buf) } .parse() .ok() .expect("Parse error.") } pub fn read_vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> { (0..n).map(|_| self.read()).collect() } pub fn chars(&mut self) -> Vec<char> { self.read::<String>().chars().collect() } }
AtCoder Regular Contest 059 E - キャンディーとN人の子供 / Children and Candies
コード
use self::mod_int::ModInt; const MOD: usize = 1e9 as usize + 7; fn main() { let stdin = std::io::stdin(); let mut sc = Scanner { reader: stdin.lock(), }; let n: usize = sc.read(); let c: usize = sc.read(); let a: Vec<usize> = sc.read_vec(n); let b: Vec<usize> = sc.read_vec(n); let b_max: usize = *b.iter().max().unwrap(); // pow[i][j] := i**j let mut pow = vec![vec![ModInt::new(0); c + 1]; b_max + 1]; for i in 1..(b_max + 1) { pow[i][0] = ModInt::new(1); for j in 0..c { pow[i][j + 1] = pow[i][j] * i; } } // sum[i][c] := sum(pow[a[i]..b[i]+1][c]) let mut sum = vec![vec![ModInt::new(0); c + 1]; n]; for i in 0..n { let from = a[i]; let to = b[i]; for c in 0..(c + 1) { for t in from..(to + 1) { sum[i][c] += pow[t][c]; } } } let mut dp = vec![ModInt::new(0); c + 1]; dp[0] = ModInt::new(1); for i in 0..n { let mut next = vec![ModInt::new(0); c + 1]; for from in 0..(c + 1) { for add in 0..(c + 1) { if from + add > c { continue; } next[from + add] += dp[from] * sum[i][add]; } } dp = next; } println!("{}", dp[c].value); } pub mod mod_int { use std::ops::{Add, AddAssign, Mul, MulAssign, Rem, Sub, SubAssign}; #[derive(Copy)] pub struct ModInt<T> { pub value: T, modulo: T, } impl<T> Clone for ModInt<T> where T: Copy, { fn clone(&self) -> Self { ModInt { value: self.value, modulo: self.modulo, } } fn clone_from(&mut self, source: &ModInt<T>) { self.value = source.value; self.modulo = source.modulo; } } impl<T> Add<ModInt<T>> for ModInt<T> where T: Add<Output = T> + Sub<Output = T> + Copy + PartialOrd, { type Output = ModInt<T>; fn add(self, rhs: ModInt<T>) -> ModInt<T> { self + rhs.value } } impl<T> Add<T> for ModInt<T> where T: Add<Output = T> + Sub<Output = T> + Copy + PartialOrd, { type Output = ModInt<T>; fn add(self, rhs: T) -> ModInt<T> { let m = self.modulo; let mut t = rhs + self.value; if t >= m { t = t - m; } ModInt { value: t, modulo: self.modulo, } } } impl<T> Sub<T> for ModInt<T> where T: PartialOrd + Copy + Add<Output = T> + Sub<Output = T> + Rem<Output = T>, { type Output = ModInt<T>; fn sub(self, rhs: T) -> ModInt<T> { let rhs = if rhs >= self.modulo { rhs % self.modulo } else { rhs }; let value = if self.value < rhs { self.value + self.modulo } else { self.value }; ModInt { value: value - rhs, modulo: self.modulo, } } } impl<T> Sub<ModInt<T>> for ModInt<T> where T: PartialOrd + Copy + Add<Output = T> + Sub<Output = T> + Rem<Output = T>, { type Output = ModInt<T>; fn sub(self, rhs: ModInt<T>) -> ModInt<T> { self - rhs.value } } impl<T> AddAssign<T> for ModInt<T> where T: Add<Output = T> + Sub<Output = T> + Copy + PartialOrd, { fn add_assign(&mut self, other: T) { *self = *self + other; } } impl<T> AddAssign<ModInt<T>> for ModInt<T> where T: Add<Output = T> + Sub<Output = T> + Copy + PartialOrd, { fn add_assign(&mut self, other: ModInt<T>) { *self = *self + other; } } impl<T> SubAssign<T> for ModInt<T> where T: PartialOrd + Copy + Add<Output = T> + Sub<Output = T> + Rem<Output = T>, { fn sub_assign(&mut self, other: T) { *self = *self - other; } } impl<T> SubAssign<ModInt<T>> for ModInt<T> where T: PartialOrd + Copy + Add<Output = T> + Sub<Output = T> + Rem<Output = T>, { fn sub_assign(&mut self, other: ModInt<T>) { *self = *self - other; } } impl<T> Mul<ModInt<T>> for ModInt<T> where T: Mul<Output = T> + Rem<Output = T> + Copy, { type Output = ModInt<T>; fn mul(self, rhs: ModInt<T>) -> ModInt<T> { self * rhs.value } } impl<T> Mul<T> for ModInt<T> where T: Mul<Output = T> + Rem<Output = T> + Copy, { type Output = ModInt<T>; fn mul(self, rhs: T) -> ModInt<T> { let t = (self.value * rhs) % self.modulo; ModInt { value: t, modulo: self.modulo, } } } impl<T> MulAssign<T> for ModInt<T> where T: Mul<Output = T> + Rem<Output = T> + Copy, { fn mul_assign(&mut self, rhs: T) { *self = *self * rhs; } } impl<T> MulAssign<ModInt<T>> for ModInt<T> where T: Mul<Output = T> + Rem<Output = T> + Copy, { fn mul_assign(&mut self, rhs: ModInt<T>) { *self = *self * rhs; } } impl ModInt<usize> { pub fn new(value: usize) -> Self { ModInt { value: value, modulo: self::super::MOD, } } } } pub struct Scanner<R> { reader: R, } impl<R: std::io::Read> Scanner<R> { pub fn read<T: std::str::FromStr>(&mut self) -> T { use std::io::Read; let buf = self .reader .by_ref() .bytes() .map(|b| b.unwrap()) .skip_while(|&b| b == b' ' || b == b'\n') .take_while(|&b| b != b' ' && b != b'\n') .collect::<Vec<_>>(); unsafe { std::str::from_utf8_unchecked(&buf) } .parse() .ok() .expect("Parse error.") } pub fn read_vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> { (0..n).map(|_| self.read()).collect() } pub fn chars(&mut self) -> Vec<char> { self.read::<String>().chars().collect() } }
CODE FESTIVAL 2018 qual A D - 通勤
解法
公式解説を見ながらやった。
地点 i で給油した時、残り容量は必ず f になる。x[i] + f - t までは少なくとも t 以下にはならないので、 x[i] から x[i] + f - t までの間にある給油所は、あってもなくても良い。また、iのあと給油せずにx[i] + fを超えると残量がゼロになってしまうので、x[i]+f-tからx[i]+fの間で必ず給油しなければならない。
dp[i] を i で給油する組み合わせの数とすると、ナイーブな 更新式は以下のように書ける。
for i in 0..n {
let from = x.upper_bound(x[i] + f - t);
let to = x.upper_bound(x[i] + f);
let skip = from - 1 - i;
let combinations = dp[i] * pow2[skip];
for j in from..to {
dp[j] += combinations;
}
}これは累積和の性質を使って更新部分を高速化出来る。
コード
use self::mod_int::ModInt; const MOD: usize = 1e9 as usize + 7; fn main() { let mut sc = Scanner::new(); let d: usize = sc.read(); let f: usize = sc.read(); let t: usize = sc.read(); let n: usize = sc.read(); let mut x: Vec<usize> = sc.read_vec(n); let mut pow2 = vec![ModInt::new(1); n + 1]; for i in 0..n { pow2[i + 1] = pow2[i] * 2; } x.insert(0, 0); x.push(d); let n = x.len(); let mut dp = vec![ModInt::new(0); n + 1]; dp[0] = ModInt::new(1); let mut sum = vec![ModInt::new(0); n + 1]; for i in 0..n { if i > 0 { sum[i] += sum[i - 1]; dp[i] = sum[i]; } let from = x.upper_bound(x[i] + f - t); let to = x.upper_bound(x[i] + f); let skip = from - 1 - i; let combinations = dp[i] * pow2[skip]; if from < dp.len() { sum[from] += combinations; } if to < dp.len() { sum[to] -= combinations; } } let mut ans = ModInt::new(0); for i in 0..(n - 1) { if x[n - 1] - x[i] <= f - t { let skip = (n - 1) - 1 - i; ans += dp[i] * pow2[skip]; } } ans += dp[n - 1]; println!("{}", ans.value); } struct Scanner { ptr: usize, length: usize, buf: Vec<u8>, small_cache: Vec<u8>, } #[allow(dead_code)] impl Scanner { fn new() -> Scanner { Scanner { ptr: 0, length: 0, buf: vec![0; 1024], small_cache: vec![0; 1024], } } fn load(&mut self) { use std::io::Read; let mut s = std::io::stdin(); self.length = s.read(&mut self.buf).unwrap(); } fn byte(&mut self) -> u8 { if self.ptr >= self.length { self.ptr = 0; self.load(); if self.length == 0 { self.buf[0] = b'\n'; self.length = 1; } } self.ptr += 1; return self.buf[self.ptr - 1]; } fn is_space(b: u8) -> bool { b == b'\n' || b == b'\r' || b == b'\t' || b == b' ' } fn read_vec<T>(&mut self, n: usize) -> Vec<T> where T: std::str::FromStr, T::Err: std::fmt::Debug, { (0..n).map(|_| self.read()).collect() } fn read<T>(&mut self) -> T where T: std::str::FromStr, T::Err: std::fmt::Debug, { let mut b = self.byte(); while Scanner::is_space(b) { b = self.byte(); } for pos in 0..self.small_cache.len() { self.small_cache[pos] = b; b = self.byte(); if Scanner::is_space(b) { return String::from_utf8_lossy(&self.small_cache[0..(pos + 1)]) .parse() .unwrap(); } } let mut v = self.small_cache.clone(); while !Scanner::is_space(b) { v.push(b); b = self.byte(); } return String::from_utf8_lossy(&v).parse().unwrap(); } } trait VecBound { fn upper_bound(&self, x: usize) -> usize; } impl VecBound for Vec<usize> { fn upper_bound(&self, x: usize) -> usize { self.binary_search_by_key(&(x * 2 + 1), |&v| v * 2) .err() .unwrap() } } pub mod mod_int { use std::ops::{Add, AddAssign, Mul, MulAssign, Rem, Sub, SubAssign}; #[derive(Copy)] pub struct ModInt<T> { pub value: T, modulo: T, } impl<T> Clone for ModInt<T> where T: Copy, { fn clone(&self) -> Self { ModInt { value: self.value, modulo: self.modulo, } } fn clone_from(&mut self, source: &ModInt<T>) { self.value = source.value; self.modulo = source.modulo; } } impl<T> Add<ModInt<T>> for ModInt<T> where T: Add<Output = T> + Sub<Output = T> + Copy + PartialOrd, { type Output = ModInt<T>; fn add(self, rhs: ModInt<T>) -> ModInt<T> { self + rhs.value } } impl<T> Add<T> for ModInt<T> where T: Add<Output = T> + Sub<Output = T> + Copy + PartialOrd, { type Output = ModInt<T>; fn add(self, rhs: T) -> ModInt<T> { let m = self.modulo; let mut t = rhs + self.value; if t >= m { t = t - m; } ModInt { value: t, modulo: self.modulo, } } } impl<T> Sub<T> for ModInt<T> where T: PartialOrd + Copy + Add<Output = T> + Sub<Output = T> + Rem<Output = T>, { type Output = ModInt<T>; fn sub(self, rhs: T) -> ModInt<T> { let rhs = if rhs >= self.modulo { rhs % self.modulo } else { rhs }; let value = if self.value < rhs { self.value + self.modulo } else { self.value }; ModInt { value: value - rhs, modulo: self.modulo, } } } impl<T> Sub<ModInt<T>> for ModInt<T> where T: PartialOrd + Copy + Add<Output = T> + Sub<Output = T> + Rem<Output = T>, { type Output = ModInt<T>; fn sub(self, rhs: ModInt<T>) -> ModInt<T> { self - rhs.value } } impl<T> AddAssign<T> for ModInt<T> where T: Add<Output = T> + Sub<Output = T> + Copy + PartialOrd, { fn add_assign(&mut self, other: T) { *self = *self + other; } } impl<T> AddAssign<ModInt<T>> for ModInt<T> where T: Add<Output = T> + Sub<Output = T> + Copy + PartialOrd, { fn add_assign(&mut self, other: ModInt<T>) { *self = *self + other; } } impl<T> SubAssign<T> for ModInt<T> where T: PartialOrd + Copy + Add<Output = T> + Sub<Output = T> + Rem<Output = T>, { fn sub_assign(&mut self, other: T) { *self = *self - other; } } impl<T> SubAssign<ModInt<T>> for ModInt<T> where T: PartialOrd + Copy + Add<Output = T> + Sub<Output = T> + Rem<Output = T>, { fn sub_assign(&mut self, other: ModInt<T>) { *self = *self - other; } } impl<T> Mul<ModInt<T>> for ModInt<T> where T: Mul<Output = T> + Rem<Output = T> + Copy, { type Output = ModInt<T>; fn mul(self, rhs: ModInt<T>) -> ModInt<T> { self * rhs.value } } impl<T> Mul<T> for ModInt<T> where T: Mul<Output = T> + Rem<Output = T> + Copy, { type Output = ModInt<T>; fn mul(self, rhs: T) -> ModInt<T> { let t = (self.value * rhs) % self.modulo; ModInt { value: t, modulo: self.modulo, } } } impl<T> MulAssign<T> for ModInt<T> where T: Mul<Output = T> + Rem<Output = T> + Copy, { fn mul_assign(&mut self, rhs: T) { *self = *self * rhs; } } impl<T> MulAssign<ModInt<T>> for ModInt<T> where T: Mul<Output = T> + Rem<Output = T> + Copy, { fn mul_assign(&mut self, rhs: ModInt<T>) { *self = *self * rhs; } } impl ModInt<usize> { pub fn new(value: usize) -> Self { ModInt { value: value, modulo: super::MOD, } } } }
AOJ 2893: Balanced Edge Deletion
解法
橋を全列挙し、それぞれについて削除したときの cost を求め、ソートすれば良い。
具体的な実装としては、
- 橋を列挙する。
- 橋を含まない連結な部分グラフを潰して 1 つの頂点とし、橋を辺とする木を作る。
- 木 DP をして、各橋を削除したときのコストを求める。
コード
/// Thank you tanakh!!! /// https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8 macro_rules! input { (source = $s:expr, $($r:tt)*) => { let mut iter = $s.split_whitespace(); input_inner!{iter, $($r)*} }; ($($r:tt)*) => { let mut s = { use std::io::Read; let mut s = String::new(); std::io::stdin().read_to_string(&mut s).unwrap(); s }; let mut iter = s.split_whitespace(); input_inner!{iter, $($r)*} }; } macro_rules! input_inner { ($iter:expr) => {}; ($iter:expr, ) => {}; ($iter:expr, $var:ident : $t:tt $($r:tt)*) => { let $var = read_value!($iter, $t); input_inner!{$iter $($r)*} }; } macro_rules! read_value { ($iter:expr, ( $($t:tt),* )) => { ( $(read_value!($iter, $t)),* ) }; ($iter:expr, [ $t:tt ; $len:expr ]) => { (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>() }; ($iter:expr, chars) => { read_value!($iter, String).chars().collect::<Vec<char>>() }; ($iter:expr, usize1) => { read_value!($iter, usize) - 1 }; ($iter:expr, $t:ty) => { $iter.next().unwrap().parse::<$t>().expect("Parse error") }; } use std::cmp; use std::collections::{BTreeMap, BTreeSet}; fn main() { input!(n: usize, m: usize, uvw: [(usize1, usize1, usize); m]); let mut graph = vec![vec![]; n]; for &(u, v, _) in uvw.iter() { graph[u].push(v); graph[v].push(u); } let mut union_find = UnionFind::new(n); let bridges = BridgeDetector::new(&graph) .bridges .iter() .map(|&(u, v)| (cmp::min(u, v), cmp::max(u, v))) .collect::<BTreeSet<_>>(); let mut edges = vec![]; for &(u, v, w) in uvw.iter() { assert!(u < v); if bridges.contains(&(u, v)) { edges.push((u, v, w)); continue; } union_find.unite(u, v); } let mut convert = BTreeMap::new(); for i in 0..n { let parent = union_find.find(i); if convert.contains_key(&parent) { continue; } let n = convert.len(); convert.insert(parent, n); } let n = convert.len(); let mut costs = vec![0; n]; for &(u, v, w) in uvw.iter() { if union_find.find(u) == union_find.find(v) { let parent = union_find.find(u); let i = *convert.get(&parent).unwrap(); costs[i] += w; } } let edges = edges .iter() .map(|&(u, v, w)| { let u = union_find.find(u); let v = union_find.find(v); assert!(u != v); let u = *convert.get(&u).unwrap(); let v = *convert.get(&v).unwrap(); (u, v, w) }).collect::<Vec<_>>(); let mut graph = vec![vec![]; n]; for &(u, v, w) in edges.iter() { graph[u].push((v, w)); graph[v].push((u, w)); } dfs(0, 0, &graph, &mut costs); let sum = uvw.iter().map(|&(_, _, w)| w).sum::<usize>(); let mut candidates = uvw .iter() .map(|&(u, v, w)| { if union_find.find(u) == union_find.find(v) { (sum - w, u, v) } else { let fu = *convert.get(&union_find.find(u)).unwrap(); let fv = *convert.get(&union_find.find(v)).unwrap(); let cost = cmp::min(costs[fu], costs[fv]); let other = sum - cost - w; (cmp::max(other, cost) - cmp::min(other, cost), u, v) } }).collect::<Vec<_>>(); candidates.sort(); let (_, u, v) = candidates[0]; println!("{} {}", u + 1, v + 1); } fn dfs(v: usize, parent: usize, graph: &Vec<Vec<(usize, usize)>>, costs: &mut Vec<usize>) -> usize { for &(child, w) in graph[v].iter() { if child != parent { let c = dfs(child, v, graph, costs); costs[v] += c + w; } } costs[v] } pub struct UnionFind { parent: Vec<usize>, sizes: Vec<usize>, size: usize, } impl UnionFind { pub fn new(n: usize) -> UnionFind { UnionFind { parent: (0..n).map(|i| i).collect::<Vec<usize>>(), sizes: vec![1; n], size: n, } } pub fn find(&mut self, x: usize) -> usize { if x == self.parent[x] { x } else { let px = self.parent[x]; self.parent[x] = self.find(px); self.parent[x] } } pub fn unite(&mut self, x: usize, y: usize) -> bool { let parent_x = self.find(x); let parent_y = self.find(y); if parent_x == parent_y { return false; } let (large, small) = if self.sizes[parent_x] < self.sizes[parent_y] { (parent_y, parent_x) } else { (parent_x, parent_y) }; self.parent[small] = large; self.sizes[large] += self.sizes[small]; self.sizes[small] = 0; self.size -= 1; return true; } } pub struct BridgeDetector { articulations: Vec<usize>, bridges: Vec<(usize, usize)>, visit: Vec<bool>, order: Vec<usize>, low_link: Vec<usize>, k: usize, } impl BridgeDetector { pub fn new(graph: &Vec<Vec<usize>>) -> Self { let n = graph.len(); let mut d = BridgeDetector { articulations: vec![], bridges: vec![], visit: vec![false; n], order: vec![0; n], low_link: vec![0; n], k: 0, }; d.run(graph); d } fn run(&mut self, graph: &Vec<Vec<usize>>) { let n = graph.len(); for i in 0..n { if !self.visit[i] { self.dfs(i, 0, graph, i); } } } fn dfs(&mut self, v: usize, previous: usize, graph: &Vec<Vec<usize>>, root: usize) { self.visit[v] = true; self.order[v] = self.k; self.k += 1; self.low_link[v] = self.order[v]; let mut is_articulation = false; let mut dimension = 0; for &next in graph[v].iter() { if !self.visit[next] { // The edge (v->next) is not a backedge. dimension += 1; self.dfs(next, v, graph, root); self.low_link[v] = cmp::min(self.low_link[v], self.low_link[next]); if v != root && self.order[v] <= self.low_link[next] { is_articulation = true; } if self.order[v] < self.low_link[next] { let min = cmp::min(v, next); let max = cmp::max(v, next); self.bridges.push((min, max)); } } else if v == root || next != previous { // The edge (v->next) is a backedge. self.low_link[v] = cmp::min(self.low_link[v], self.order[next]); } } if v == root && dimension > 1 { is_articulation = true; } if is_articulation { self.articulations.push(v); } } }
