結果
問題 | No.1817 Reversed Edges |
ユーザー | phspls |
提出日時 | 2022-10-14 00:23:35 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 185 ms / 2,000 ms |
コード長 | 1,799 bytes |
コンパイル時間 | 12,918 ms |
コンパイル使用メモリ | 402,156 KB |
実行使用メモリ | 19,024 KB |
最終ジャッジ日時 | 2024-06-26 12:15:27 |
合計ジャッジ時間 | 18,115 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 23 |
ソースコード
use std::collections::VecDeque; fn dfs(cur: usize, prev: usize, paths: &Vec<Vec<usize>>, parents: &mut Vec<usize>) { parents[cur] = prev; for &v in paths[cur].iter() { if v == prev { continue; } dfs(v, cur, paths, parents); } } fn main() { let mut n = String::new(); std::io::stdin().read_line(&mut n).ok(); let n: usize = n.trim().parse().unwrap(); let mut paths = vec![vec![]; n]; let mut lines = Vec::with_capacity(n-1); for _ in 0..n-1 { let mut ab = String::new(); std::io::stdin().read_line(&mut ab).ok(); let ab: Vec<usize> = ab.trim().split_whitespace().map(|s| s.parse().unwrap()).collect(); let a = ab[0]-1; let b = ab[1]-1; paths[a].push(b); paths[b].push(a); lines.push((a, b)); } let mut parents = vec![n-1; n]; dfs(n-1, n-1, &paths, &mut parents); let mut vals = vec![0isize; n]; for &(a, b) in lines.iter() { if a > b { if parents[b] == a { vals[b] -= 1; vals[n-1] += 1; } else { vals[a] += 1; } } else { if parents[a] == b { vals[a] -= 1; vals[n-1] += 1; } else { vals[b] += 1; } } } let mut result = vec![0isize; n]; result[n-1] = vals[n-1]; let mut deque = VecDeque::new(); deque.push_back((n-1, vals[n-1])); while let Some((u, val)) = deque.pop_front() { for &v in paths[u].iter() { if v == parents[u] { continue; } let nval = val + vals[v]; result[v] = nval; deque.push_back((v, nval)); } } for &v in result.iter() { println!("{}", v); } }