結果
問題 |
No.763 Noelちゃんと木遊び
|
ユーザー |
|
提出日時 | 2024-08-19 11:28:43 |
言語 | Rust (1.83.0 + proconio) |
結果 |
WA
|
実行時間 | - |
コード長 | 959 bytes |
コンパイル時間 | 14,308 ms |
コンパイル使用メモリ | 401,680 KB |
実行使用メモリ | 15,488 KB |
最終ジャッジ日時 | 2024-08-19 11:29:04 |
合計ジャッジ時間 | 17,066 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 1 WA * 20 |
ソースコード
use std::collections::BTreeSet; 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[u]+=1; indegs[v]+=1; } let mut st=(0..n).map(|i|(indegs[i],i)).collect::<BTreeSet<_>>(); let mut deled = vec![false; n]; while let Some((indeg, crr)) = st.pop_last() { if indeg <= 1 { continue; } deled[crr] = true; for &nxt in g[crr].iter() { if deled[nxt] { continue; } st.remove(&(indegs[nxt],nxt)); indegs[nxt] -= 1; st.insert((indegs[nxt], nxt)); } } let ans=deled.iter().filter(|&&del|!del).count()-(0..n).filter(|&i|!deled[i]&&indegs[i]>=1).count()/2; println!("{}", ans); }