結果
問題 | No.2888 Mamehinata |
ユーザー | Yukino DX. |
提出日時 | 2024-10-16 21:28:43 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 382 ms / 2,000 ms |
コード長 | 1,239 bytes |
コンパイル時間 | 16,774 ms |
コンパイル使用メモリ | 379,188 KB |
実行使用メモリ | 25,868 KB |
最終ジャッジ日時 | 2024-10-16 21:29:14 |
合計ジャッジ時間 | 28,149 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 52 |
ソースコード
use std::collections::VecDeque; use proconio::{input, marker::Usize1}; fn main() { input! { n:usize, m:usize, uv:[(Usize1,Usize1);m], } let mut g = vec![vec![]; n]; for &(u, v) in uv.iter() { g[u].push(v); g[v].push(u); } if g[0].is_empty() { for _ in 0..n { println!("0"); } return; } let mut q = VecDeque::new(); let mut dists = vec![n + 1; n]; dists[0] = 0; q.push_back(0); while let Some(crr) = q.pop_front() { for &nxt in g[crr].iter() { if dists[nxt] != n + 1 { continue; } dists[nxt] = dists[crr] + 1; q.push_back(nxt); } } dists[0] = 2; let mut ans = vec![0; n]; let mut add_odd = 0; let mut add_even = 0; dists.sort(); let mut ind = 0; for i in 1..=n { while ind < n && dists[ind] == i { if i % 2 == 0 { add_even += 1; } else { add_odd += 1; } ind += 1; } ans[i - 1] = if i % 2 == 0 { add_even } else { add_odd }; } for i in 0..n { println!("{}", ans[i]); } }