結果
問題 |
No.1424 Ultrapalindrome
|
ユーザー |
|
提出日時 | 2022-12-06 00:17:15 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 43 ms / 2,000 ms |
コード長 | 2,434 bytes |
コンパイル時間 | 12,926 ms |
コンパイル使用メモリ | 379,136 KB |
実行使用メモリ | 20,572 KB |
最終ジャッジ日時 | 2024-10-12 20:17:43 |
合計ジャッジ時間 | 15,637 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 29 |
コンパイルメッセージ
warning: unused variable: `n` --> src/main.rs:21:9 | 21 | let n = paths.len(); | ^ help: if this is intentional, prefix it with an underscore: `_n` | = note: `#[warn(unused_variables)]` on by default
ソースコード
use std::collections::{VecDeque, HashSet}; const INF: usize = 1usize << 60; fn tree_diameter(paths: &Vec<Vec<(usize, usize)>>) -> (usize, usize, usize) { fn calc(paths: &Vec<Vec<(usize, usize)>>, start: usize) -> Vec<usize> { let n = paths.len(); let mut costs = vec![INF; n]; costs[start] = 0usize; let mut deq = VecDeque::new(); deq.push_back(start); while let Some(u) = deq.pop_front() { for &(v, cost) in paths[u].iter() { if costs[v] < INF { continue; } costs[v] = costs[v].min(costs[u] + cost); deq.push_back(v); } } costs } let n = paths.len(); let costs = calc(paths, 0); let idx = costs.into_iter().enumerate().max_by_key(|&(_, c)| c).unwrap().0; let costs = calc(paths, idx); let ridx = costs.into_iter().enumerate().max_by_key(|&(_, c)| c).unwrap(); // start_point, end_point, cost (idx, ridx.0, ridx.1) } fn dfs(cur: usize, prev: usize, paths: &Vec<Vec<(usize, usize)>>, depth: &mut usize, dists: &mut Vec<usize>) { dists[cur] = *depth; for &(v, _) in paths[cur].iter() { if v == prev { continue; } *depth += 1; dfs(v, cur, paths, depth, dists); *depth -= 1; } } 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]; for _ in 0..n-1 { let mut temp = String::new(); std::io::stdin().read_line(&mut temp).ok(); let temp: Vec<usize> = temp.trim().split_whitespace().map(|s| s.parse().unwrap()).collect(); let a = temp[0]-1; let b = temp[1]-1; paths[a].push((b, 1)); paths[b].push((a, 1)); } let tries = paths.iter().filter(|&v| v.len() > 2).count(); if tries == 0 { println!("Yes"); return; } else if tries > 1 { println!("No"); return; } let (start, end, _) = tree_diameter(&paths); let mut dists = vec![0usize; n]; for &i in vec![start, end].iter() { let mut depth = 0usize; dfs(i, i, &paths, &mut depth, &mut dists); if dists.iter().enumerate().filter(|&(j, _)| i != j && paths[j].len() == 1).map(|(_, &v)| v).collect::<HashSet<usize>>().len() > 1 { println!("No"); return; } } println!("Yes"); }