結果
問題 |
No.763 Noelちゃんと木遊び
|
ユーザー |
|
提出日時 | 2024-08-19 10:52:21 |
言語 | Rust (1.83.0 + proconio) |
結果 |
WA
|
実行時間 | - |
コード長 | 946 bytes |
コンパイル時間 | 14,551 ms |
コンパイル使用メモリ | 399,968 KB |
実行使用メモリ | 13,952 KB |
最終ジャッジ日時 | 2024-08-19 10:52:39 |
合計ジャッジ時間 | 15,361 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 1 WA * 20 |
ソースコード
use std::collections::BinaryHeap; use proconio::{input, marker::Usize1}; fn main() { input! { n:usize, uv:[(Usize1,Usize1);n-1], } let mut indegs = vec![0; n]; let mut g = vec![vec![]; n]; for &(u, v) in uv.iter() { g[u].push(v); g[v].push(u); indegs[v] += 1; indegs[u] += 1; } let mut ans = 1; let mut pq = (0..n).map(|i| (indegs[i], i)).collect::<BinaryHeap<_>>(); let mut deled = vec![false; n]; while let Some((indeg, crr)) = pq.pop() { if indegs[crr] < indeg || indeg <= 1 { continue; } deled[crr] = true; ans += indeg - 1; // println!("indeg:{} crr:{} ans:{}",indeg,crr,ans); for &nxt in g[crr].iter() { if deled[nxt] { continue; } indegs[nxt] -= 1; pq.push((indegs[nxt], nxt)); } } println!("{}", ans); }